518.零钱兑换||
题目：518. 零钱兑换 II - 力扣（LeetCode）
思路：组合问题，应该用的递推公式跟目标和是一样的
尝试（参考目标和递推公式，以及完全背包遍历for循环，AC）
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];}
}答案
class Solution {public int change(int amount, int[] coins) {//递推表达式int[] dp = new int[amount + 1];//初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装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];}
}小结
- dp[j]：凑成总金额j的货币组合数为dp[j]
- 求装满背包有几种方法，公式都是：dp[j] += dp[ j - nums[i] ];
- dp[0] = 1是 递归公式的基础。
377.组合总和IV
题目：377. 组合总和 Ⅳ - 力扣（LeetCode）
思路：有点难的是，这个是要考虑排序的，不同顺序会被视为不同的组合，想不出来
答案
class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target + 1];dp[0] = 1;for (int i = 0; i <= target; i++) {for (int j = 0; j < nums.length; j++) {if (i >= nums[j]) {dp[i] += dp[i - nums[j]];}}}return dp[target];}
}小结
- dp[i]: 凑成目标正整数为i的排列个数为dp[i]
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
