零钱兑换
动态规划
dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
得到dp[j]，只有一个来源，dp[j - coins[i]]。
凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]
递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount+1 ,INT_MAX); dp[0]=0; for(int i=0 ; i<coins.size() ; i++) { for(int j=0 ; j<=amount ;j++) { if(j>=coins[i] && dp[j-coins[i]] != INT_MAX) { dp[j] = min( dp[j], dp[j-coins[i]] + 1); } } } if(dp[amount]==INT_MAX) return -1; return dp[amount]; } };
二刷
class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount+1 , INT_MAX); dp[0] = 0; for(int i=0 ; i<coins.size();i++) { for(int j=coins[i]; j<=amount ; j++) { if(dp[j-coins[i]]!=INT_MAX) dp[j] = min(dp[j] , dp[j-coins[i]]+1); } } if(dp[amount] == INT_MAX) return -1; return dp[amount]; } };
