力扣第37天----第322题、第279题

力扣第37天----第322题、第279题

一、第322题–零钱兑换

​ 整体思路，跟前面的几道完全背包差不多，就不具体解释了。有一些细节要注意，见代码注释。

class Solution {
public:int coinChange(vector<int>& coins, int amount) {if (amount == 0) return 0; vector<int> dp(amount+1, INT_MAX);  //求最小值，设为INT_MAX，并使用其初始化。dp[0] = 0;                          //第0个元素，初始化为0for(int i = 0; i < coins.size(); ++i){for (int j = coins[i]; j<dp.size(); ++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;    //不满足题意时，返回-1。即，元素没有被改变，还是初始化值--INT_MAX。return dp[amount];}
};

二、第279题–组合总和 Ⅳ

​ 跟上一题，基本一样。没啥太多好说的。

class Solution {
public:int numSquares(int n) {vector<int> dp(n+1, INT_MAX);dp[0] = 0;for(int i = 1; i*i <= n; ++i){for (int j = i*i; j < dp.size(); ++j){//cout << dp[j] << ' ';dp[j] = min(dp[j], dp[j - i*i]+1);}}return dp[n];}
};