完全背包问题
相对于0-1背包，主要区别点在于物品可以使用无限次
0-1背包的dp状态转移方程
// 01背包
for (int i = 0; i < weight.length; i++) {
// 从后往前遍历背包容量
for (int j = cap; j >= weight[i]; j--) {
dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
}
}
完全背包的dp状态转移方程
// 完全背包
for (int i = 0; i < weight.length;; i++) {
// 从前往后遍历背包容量
for (int j = weight[i]; j <= cap; j++) {
dp[j] = max(dp[j], dp[j-weight[i]] + valeu[i]);
}
}
上面那个是先遍历物品在遍历背包容量
我们还可以从另外一个角度理解完全背包：
因为所有物品可以无限次拿，定义dp数组表示 容量为n时，所装物品的最大价值
则有 f(n) = max( f(n-i) ) 0<i<=n且需要存在物品重量等于i
则可以循环物品，针对每一个小于等于n的物品，计算f(n-i)值取最大值
即
// 先循环容量、在循环物品
for (int i = 1; i <= cap; i++) {
for (int j = 0; j < weight.length; j++) {
if (weight[j] <= i) {
dp[i] = Math.max(dp[i], dp[i - weight[j]] + values[j]);
}
}
}
但是两种在使用的时候也有点区别
518. 零钱兑换 II
class Solution {
public int change(int amount, int[] coins) {
/*
完全背包问题，每个物品可以选择多次
需要注意的是需求求解的是组合数 即不考虑所选物品的顺序
完全背包 先循环物品、在循环背包
*/
int[] dp = new int[amount+1];
dp[0]=1;
for(int i=0; i<coins.length; i++){
// 正序
for(int j=coins[i]; j<=amount; j++){
dp[j]+=dp[j-coins[i]];
}
}
return dp[amount];
}
}
完全背包求方案个数，要求不考虑所选物品的顺序，即求“组合数”
这种完全背包问题就只能 先循环物品在循环背包
因为相同容量的情况下，针对两种物品如果考虑顺序就有两种方案（先选择a在选择b或先选择b在选择a），不考虑顺序就一种（一个a一个b）
377. 组合总和 Ⅳ
class Solution {
public int combinationSum4(int[] nums, int target) {
// dp：当目标值为n的时候数组中的组合方案数
// 存在递推公式：f(n) = sum( f(i) ) 0<=i<n；前提条件是 nums中要存在 n-i
// 即当数组中的元素小于等于n时，f(n-i)的和
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (num <= i) {
dp[i] += dp[i-num];
}
}
}
return dp[target];
}
}
与上题刚好相对，考虑所选物品的顺序，即求“排列数”
这种完全背包问题就只能 先循环背包早循环物品
针对每一个i<n，累计f(n-i)
322. 零钱兑换
class Solution {
public int coinChange(int[] coins, int amount) {
// 动态规划，申明dp：表示总金额n的最少硬币个数
// 存在递推公式 f(n) = min( f(i)+1 ) 0<=i<n; 前提条件是 存在n-i面额的硬币
// 也就是 组成f(i)的最少硬币数+一枚n-i面额的硬币
// 即 遍历每个硬币作为n-i存在，在加上f(i)
int[] dp = new int[amount+1];
Arrays.fill(dp, Integer.MAX_VALUE-1);
dp[0]=0;
for(int i=1; i<=amount; i++){
for(int coin: coins){
if(coin<=i){
dp[i]=Math.min(dp[i-coin]+1,dp[i]);
}
}
}
return dp[amount]==Integer.MAX_VALUE-1?-1:dp[amount];
}
}
完全背包问题求最值
最值问题，先遍历容量在遍历物品，或者先遍历物品在遍历容量，都可以
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, Integer.MAX_VALUE-1);
dp[0]=0;
for(int i=0; i<coins.length; i++){
for(int j=coins[i]; j<=amount; j++){
// 先遍历物品在遍历容量，求最值
dp[j]=Math.min(dp[j], dp[j-coins[i]]+1);
}
}
return dp[amount]==Integer.MAX_VALUE-1?-1:dp[amount];
}
279. 完全平方数
class Solution {
public int numSquares(int n) {
/*
完全背包问题，物品是完全平方数 1、4、9、16，背包容量是n
存在 f(n) = min( f(n-i) ) i是小于等于n的完全平方数
*/
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j*j <= i; j++) {
if (dp[i] == 0 || dp[i] > dp[i - j*j] + 1) {
dp[i] = dp[i - j*j] + 1;
}
}
}
return dp[n];
}
}
完全背包问题求最值
最值问题，先遍历容量在遍历物品，或者先遍历物品在遍历容量，都可以
139. 单词拆分
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int len = s.length();
// 完全背包：dp数组表示：是否能组成 s中前n个字符组成的字符串
// 则有递推公式：dp[n] = true( dp[n-i] ) 0<i<=n 且需要 字串sub(n-i,n)要在字典里面
boolean[] dp = new boolean[len + 1];
dp[0] = true;
for (int i = 1; i <= len; i++) {
String str = s.substring(0, i);
for (String word : wordDict) {
// 直接遍历物品，判断如果字典中元素是当前字符的后缀，则取dp[n-word.length]
if (str.endsWith(word)) {
dp[i] = dp[i - word.length()] || dp[i];
}
}
}
return dp[len];
}
}
完全背包求是否有值
类似于最值，先遍历容量在遍历物品，或者先遍历物品在遍历容量，都可以
总结
针对完全背包问题：
主要就是在求解方案数的时候，要看下是“排列数”还是“组合数”，选择正确的遍历顺序
如果是求解最值等问题，两种遍历顺序都可以
具体看怎么容易理解，怎么容易解决问题