代码随想录算法训练营Day37|完全背包问题、518.零钱兑换II、377. 组合总和 Ⅳ、70. 爬楼梯（进阶版）
完全背包问题
和01背包最大区别就是一个物品可以重复放多次，因此遍历空间时可以从前往后。
import java.util.*;
public class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[] weight = new int[m];int[] value = new int[m];for(int i = 0; i < m; i++){weight[i] = sc.nextInt();value[i] = sc.nextInt();}int[] dp = new int[n+1];for(int i = 0; i< weight.length; i++){for(int j = weight[i]; j<=n; j++){if(j-weight[i] >=0){dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);}}}System.out.println(dp[n]);}
}518.零钱兑换II
这题一定要手推以下dp数组才能更好理解，虽然费电时间，但感觉一点点疏通了。
dp[j] :装满j的背包，要多少种方法。
递推公式： dp[j] += dp[j-coins[i]];
凡是装满容量为[j]的背包有多少种方法，都是这个公式。
初始化：dp[0] = 1；设置为0的话地推出来都是0
遍历顺序：外层遍历物品，内层遍历背包，遍历出来是组合数。
如果反过来，外层遍历背包，内层遍历物品，遍历出来是排列数。
打印dp数组：手推的时候，我把这题类比成爬楼梯，外层遍历的是腿长，代表我一次能跨几个台阶，内层遍历的就是台阶高度了。一开始腿长只是1，到达任意台阶都只能一步一步上去，所以就是dp[j] = 1；然后能跨两步的时候，是把一步一步跨的dp[j]，加上当前台阶减去两步的最大方法数（dp[j-2]），加起来。这里计算的是方法数，不是步数，所以不需要再加1.因为在j-2的台阶往j台阶。要么一步一步跨(dp[j] 就是这种情况)，要么跨两步（就是dp[j-2]）。
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];}
}377. 组合总和 Ⅳ
如果上题手推，这题就是小葱拌豆腐，不再分析了。
class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target +1];dp[0] = 1;for(int j = 1; j <=target; j++){for(int i = 0; i< nums.length; i++){if(j-nums[i] >= 0){dp[j] += dp[j-nums[i]];}}}return dp[target];}
}70. 爬楼梯（进阶版）
在写零钱兑换题解的时候还没写这题，自己进行了类比，没想到这就来了。基本就是照抄了。
import java.util.*;public class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[] dp = new int[n+1];dp[0] = 1;for(int j = 1; j <= n; j++){for(int i =1; i <= m; i++){if(j>=i){dp[j] += dp[j - i];}}}System.out.println(dp[n]);}
}