力扣题解（完全平方数）
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
思路：
可以看成在所有满足（k*k<=n,k>=1）的所有k所组成的数组中取某些数，可以多次取同一个数，然后和为n的最小组合数，因此和零钱兑换问题实质上一样。
dp[i][j]表示前i个数，和为j的最小数量。
dp[i][j]=min(dp[i-1][j],dp[i][j-num[i]]+1)。
初始化：
i为0，j除了为0均不可能实现，因此设为一个很大的数。
j为0，对任意i，都有零个数字组成j的可能，因此dp[i][0]=0;
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n=coins.size();
int INF=0x3f3f3f3f;
vector<vector<int>>dp(n+1,vector<int>(amount+1,INF));
for(int i=0;i<=n;i++)
{
dp[i][0]=0;
}
coins.insert(coins.begin(),0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=amount;j++)
{
dp[i][j]=dp[i-1][j];
if(j-coins[i]>=0&&dp[i][j-coins[i]]!=-1)
{
// cout<<i<<j-coins[i]<<" ||";
dp[i][j]=min(dp[i][j],dp[i][j-coins[i]]+1);
}
}
}
return dp[n][amount]==INF?-1:dp[n][amount];
}
int numSquares(int n) {
vector<int>coins;
int i=1;
while(i*i<=n)
{
coins.push_back(i*i);
i++;
}
if((i-1)*(i-1)==n)
return 1;
return coinChange(coins,n);
}
};原文地址：https://blog.csdn.net/yyssas/article/details/140569106
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！