今日收获：完全背包，零钱兑换Ⅱ，组合总和Ⅳ，爬楼梯（进阶）
1. 完全背包（每种物品无限个）
题目链接：52. 携带研究材料（第七期模拟笔试） (kamacoder.com)
思路：对于01背包的一维dp数组解，倒序遍历背包容量是为了防止一个物品添加多次。反之正序遍历背包容量就可以多次添加物品，解决完全背包的问题。
方法：
import java.util.Scanner;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int N=sc.nextInt();int V=sc.nextInt();int[] weights=new int[N];int[] values=new int[N];for (int i=0;i<N;i++){weights[i]=sc.nextInt();values[i]=sc.nextInt();}// 一维背包数组int[] dp=new int[V+1];// 先遍历物品，再正序遍历背包for (int i=0;i<N;i++){for (int j=0;j<V+1;j++){if (j>=weights[i]){dp[j]=Math.max(dp[j],dp[j-weights[i]]+values[i]);}}}System.out.println(dp[V]);}
}2. 零钱兑换Ⅱ
题目链接：518. 零钱兑换 II - 力扣（LeetCode）
思路：本题属于完全背包问题的范畴，求装满背包的组合数
- dp表示总金额为 i 时的组合个数
- 初始化金额为0时的组合数为1（dp[0]=1）
- 遍历顺序是先遍历物品再正序遍历背包（零钱可以无限使用）
- 递推公式是不用当前硬币的组合数（dp[j]）再加上用当前硬币的组合数（dp[j-coins[i]]）
方法：
class Solution {public int change(int amount, int[] coins) {// 当amount为i时的组合数int[] dp=new int[amount+1];// 初始化dp[0]=1;for (int i=0;i<coins.length;i++){for (int j=1;j<amount+1;j++){if (j>=coins[i]){dp[j]+=dp[j-coins[i]];}}}return dp[amount];}
}总结：组合不要求顺序，排列则要求相同的数顺序不同则排列不同
（1）完全背包求组合数：先遍历物品再正序遍历背包。
（2）完全背包求排列数：先遍历背包再遍历物品。
3. 组合总和Ⅳ
题目链接：377. 组合总和 Ⅳ - 力扣（LeetCode）
思路：完全背包问题中求装满背包的排列个数（题目要求不同顺序视作不同的结果）。与上一题不同的是遍历顺序。
（1）如果先遍历物品后遍历背包，那么排在后面的物品只能放在已经遍历过的物品后面，求的就是组合数
（2）如果先遍历背包，后遍历物品，那么同一种结果中的物品就会有顺序上的差异，得到排列数
方法：
class Solution {public int combinationSum4(int[] nums, int target) {int len=nums.length;int[] dp=new int[target+1];// 初始化dp[0]=1;// 先正序遍历背包，后遍历物品for (int i=0;i<target+1;i++){for (int j=0;j<nums.length;j++){if (i>=nums[j]){dp[i]+=dp[i-nums[j]];}}}return dp[target];}
}4. 爬楼梯（进阶）
题目链接：57. 爬楼梯（第八期模拟笔试） (kamacoder.com)
思路：和上一题基本一样，需要爬n阶楼梯相当于容量为n的背包，每次都可以从1阶~m阶的范围中选择。
方法：
import java.util.Scanner;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 i=0;i<n+1;i++){for (int j=1;j<=m;j++){if (i>=j){dp[i]+=dp[i-j];}}}System.out.println(dp[n]);}
}
