518. Coin Change 2

思路

动态规划

• 用一个数组dp存储结果，dp[i]表示amount=i时的组合数目。
• 初始态：dp[0]=1
• 遍历所有coin,对每个coin计算coin<=i<=amout的dp值

代码（cpp）

class Solution {
public:
    int change(int amount, vector<int>& coins) {
      // dp[i]: number of combinations with amount i
      vector<int> dp(amount + 1, 0);
      dp[0] = 1;
      for(auto& coin : coins){
        for(int i = coin; i <= amount; i++)
          dp[i] += dp[i - coin];
      }
      return dp.back();
    }
};