leetcode 322. 零钱兑换

         本题属于完全背包问题，但要求最少的硬币个数。于是设定dp数组的含义dp[i]:总金额为i时，能凑成i的最少硬币个数。  需要注意初始化dp数组时，除0以外的其他地方需要初始化为INT_MAX以保证在递推过程中能被正确的覆盖。  

        代码如下：

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++){//跳过当dp[j-coins[i]]为初始值的情况if(dp[j-coins[i]] != INT_MAX){dp[j] = min(dp[j] , dp[j-coins[i]]+1);}}}if(dp[amount] == INT_MAX) return -1;else return dp[amount];}
};