代码随想录二刷 Day48

322. 零钱兑换

题还是比较简单，递推公式和之前不一样，因为之前的题目求的是达成的总共一共多少方法，如果达不成就会返回0，但是这个题问的是返回的最小数量，就要自己判断达不成的时候怎么办。这个题达不成的时候就是有格子没动的时候，这时候就返回-1；另外这个题是求最小数量，所以排列或者组合就无所谓了。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        //dp[0] = 1; 这么写是因为自己觉得后面的dp是由前面的dp推出来的
        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);   //由于这里要取最小的数量最小值，所以初始化不能都设置成0，另外这一行如果dp[j-coin[i]] 是int_max的时候你再把它加一就超过限制了。
                 }
            }
        }
        if (dp[amount] == INT_MAX) return -1;  //如果没有变动的格子就是再判断的时候跳过去的格子，无法加成这个数
        return dp[amount];
    }
};

279.完全平方数

逻辑挺简单的，有些细节还是没写对

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