给你一个整数 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);
}
};