给你一个整数?n
?,返回?和为?n
?的完全平方数的最少数量?。
完全平方数?是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1
、4
、9
?和?16
?都是完全平方数,而?3
?和?11
?不是。
示例?1:
输入:n =12
输出:3 解释:12 = 4 + 4 + 4
示例 2:
输入:n =13
输出:2 解释:13 = 4 + 9
?
提示:
1 <= n <= 10^4
解题分析
在使用动态规划解决问题时,我们通常需要一个动态规划数组,这个数组可以是一维的,二维的,甚至是三维的。数组的维度取决于我们怎样才能清晰地描述这个问题。在本题中,一维数组就足够了。
然后,我们需要设置边界条件。由于每个整数n都可以拆分为n个1的平方相加,因此我们可以先用一个for循环,从1到n,将dp[i]初始化为i。
接下来,我们需要考虑递推公式。实际上,递推公式可以翻译为:$dp[i]=\min(dp[i-1]+1,dp[i-4]+1,\ldots,dp[i-k*k]+1)$,其中$i-k*k$必须满足大于等于0。
假设当n-1时,递推公式成立,那么我们可以推导出当n时,递推公式同样成立。因此,对所有的正整数n,这个递推公式都是成立的。
最后,我们直接返回$dp[n]$,这就是我们的答案。
#include <iostream>
using namespace std;
int dp[10005];
int main(){
int n; scanf("%d",&n);
for(int i=0;i<=n;i++){
dp[i]=i;
}
for(int i=1;i<=n;i++){
for(int j=1;i-j*j>=0;j++){
dp[i]=min(dp[i],dp[i-j*j]+1);
}
}
printf("%d",dp[n]);
return 0;
}