279. 完全平方数 - 力扣（LeetCode）
总结：又是一个完全背包问题，自己这题的问题出在没有根据题意来初始化，只初始化了dp[1]，因为感觉根据题意dp[0]不需要初始化导致错误
代码：
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1,INT_MAX);
dp[0] = 0;
dp[1] = 1;
for(int i = 1;i <= n/2;i++ )//物品
{
for(int j = i * i;j <= n;j++)//背包
{
if(dp[j - i * i] != INT_MAX)
dp[j] = min(dp[j - i * i] + 1,dp[j]);
}
}
return dp[n];
}
};322. 零钱兑换 - 力扣（LeetCode）文章来源：https://www.toymoban.com/news/detail-671984.html
总结：也是一种完全背包，不过与昨天的区别在于这题是求最少所以选择min。文章来源地址https://www.toymoban.com/news/detail-671984.html
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 - coins[i]] + 1,dp[j]);
}
}
if (dp[amount] == INT_MAX) return -1;
return dp[amount];
}
};到了这里，关于算法训练第四十五天的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
