有没有可能是个数学题
保证一定能通过若干个完全平方数凑整,再不济可以11111111…
我想到了动态规划的斐波那契数列,但似乎并不是一个线性dp…
瞄评论,瞄到了“背包”,那这里应该是一个完全背包
很明显n就是背包容量…
背包是限定容量情况下能放的最大价值…
物品应该是小于n的所有完全平方数
但是这么放能保证数量最少吗?
背包的定义是前i件物品,体积不超过j所能达到的最大价值
体积等于j选中物品的最小数量
我写了个递归出来,似乎是对的,但是疯狂超时
int numSquares(int n) {
if (n == 1) return 1;
// 至多不会超过n个1组成
int minSum = n;
// 更像是一个树型dp
int i = 2;
while (pow(i, 2) <= n) {
if (pow(i, 2) == n) return 1;
else minSum = min(minSum,1+numSquares(n - pow(i, 2)));
i++;
}
return minSum;
}
啊,我应该把这个递归改成动态规划
int numSquares(int n) {
// dp[i]表示i最少由多少个完全平方数组成
vector<int> dp(n+1,n);
int j = 1;
for (int i = 1; i <= n; i++) {
j = 1;
while (pow(j, 2) <= i) {
if (pow(j, 2) == i) dp[i] = 1;
else dp[i] = min(dp[i],1 + dp[i - pow(j, 2)]);
j++;
}
// cout << dp[i] << " ";
}
return dp[n];
}
其实感觉还是差了点优雅,但是自己的思路一下子也没看出来怎么优雅
然后这题果然是个数学题,四平方和定理
标签:平方,背包,numSquares,int,完全,力扣,279,dp From: https://www.cnblogs.com/yaocy/p/16855598.html