代码随想录算法训练营day37｜动态规划part05

完全背包问题；

第一题：518. Coin Change II

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数组版本，方便理解
class Solution {public int change(int amount, int[] coins) {int[][] dp = new int[coins.length][amount+1];// 初始化边界值for(int i = 0; i < coins.length; i++){// 第一列的初始值为1dp[i][0] = 1;}for(int j = coins[0]; j <= amount; j++){// 初始化第一行dp[0][j] += dp[0][j-coins[0]];}for(int i = 1; i < coins.length; i++){for(int j = 1; j <= amount; j++){if(j < coins[i]) dp[i][j] = dp[i-1][j];else dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j];}}return dp[coins.length-1][amount];}
}

第二题：377. Combination Sum IV

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];}
}

第三题：爬楼梯进阶

感觉今天学的技巧性都挺强的，完全背包的还得再看看；

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。