零钱兑换II
完全背包
一看到钱币数量不限，就知道这是一个完全背包。
dp[j]：凑成总金额j的货币组合数为dp[j]
dp[j] （考虑coins[i]的组合总和） 就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。
所以递推公式：dp[j] += dp[j - coins[i]];
首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。
从dp[i]的含义上来讲就是，凑成总金额0的货币组合数为1。
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=0 ; j<=amount ; j++ ) { if( j>=coins[i] ) dp[j] += dp[j-coins[i]] ; else dp[j] = dp[j]; } } return dp[amount]; } };
二刷
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]; } };
