代码随想录算法训练营第37天 | 518.零钱兑换II

2025-07-03

518.零钱兑换II

• 因为没有看之前的内容理解起来有点困难，所以看了一遍0-1背包的理论基础
• 一维dp数组是从二维dp数组转化而来
• 二维dp数组的递推公式

  dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]

  • 含义：使用[0,i]个零钱，零钱总和为j的组合数
  • 这里需要注意的是，为什么是dp[i][j-coins[i]]而不是dp[i-1][j-coins[i]]。是因为每个零钱是无数个的，可以重复使用的。
  • 而且这个是滚动数组！！
• 转换成一维dp数组

  dp[j] = dp[j] + dp[j - coins[i]]

• 遍历顺序：先遍历零钱，还是遍历总和
  • 这个取决于要找的是组合，而不是排列。所以要先遍历零钱

class Solution {
    public int change(int amount, int[] coins) {
        int dp[] = new int[amount+1];
        dp[0] = 1; // 这个我不懂。装满背包容量为0 的方法是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];
    }
}