518.coin-change-2.md

• 518. 零钱兑换 II

---

完全背包问题

dp[i]表示方案数

算法思路：

枚举物品

​ 枚举体积

​ 计算方案数

代码实现

java

class Solution {
    public int change(int V, int[] c) {
        int dp[] = new int[V+1];
        dp[0] = 1;

        for (int x : c){
            for (int v = x; v <=V; v++ ){
                dp[v] += dp[v-x];
            }
        }
        return dp[V];
    }
}

javascript

var change = function (amount, coins) {
  let dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (let c of coins) {
    for (let i = c; i <= amount; i++) {
      dp[i] = dp[i - c] + dp[i];
    }
  }
  return dp[amount];
};

c++

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for (int i = 0; i< coins.size(); i++){
            for (int j = coins[i]; j <= amount; j++){
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
};