【算法挨揍日记】day44——518. 零钱兑换 II、279. 完全平方数

?518. 零钱兑换 II

518.?零钱兑换 II

题目描述：

给你一个整数数组?coins?表示不同面额的硬币，另给一个整数?amount?表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回?0?。

假设每一种面额的硬币有无限个。?

题目数据保证结果符合 32 位带符号整数。

解题思路：

解题思路：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n=coins.size();
        vector<vector<int>>dp(n+1,vector<int>(amount+1));
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=amount;j++)
            {
                dp[i][j]+=dp[i-1][j];
                if(j>=coins[i-1]) dp[i][j]+=dp[i][j-coins[i-1]];
            }
        }
        return dp[n][amount];
    }
};

?空间优化后的代码：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n=coins.size();
        vector<int>dp(amount+1);
        dp[0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=coins[i-1];j<=amount;j++)
            {
                dp[j]+=dp[j-coins[i-1]];
            }
        }
        return dp[amount];
    }
};

?279. 完全平方数

279.?完全平方数

题目描述：

给你一个整数?n?，返回?和为?n?的完全平方数的最少数量?。

完全平方数?是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9?和?16?都是完全平方数，而?3?和?11?不是。

解题思路：

解题代码：

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1);
        dp[1] = 1;                   // 初始化
        for (int i = 2; i <= n; i++) // 枚举每个数
        {
            dp[i] = 1 + dp[i - 1];           // ?少等于 1 + dp[i - 1]
            for (int j = 2; j * j <= i; j++) // ??于 i 的完全平?数划分区间
                dp[i] =
                    min(dp[i], dp[i - j * j] + 1); // 拿到所有划分区间内的最?值
        }
        // 返回结果
        return dp[n];
    }
};

”