简答题
偏难
#20888
小杨和整数拆分 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有一个正整数n,小杨想将它拆分成若干完全平方数的和,同时小杨希望拆分的数量越少越…
小杨和整数拆分
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一个正整数n,小杨想将它拆分成若干完全平方数的和,同时小杨希望拆分的数量越少越好。
小杨请你编写程序计算出总和为n 的完全平方数的最少数量。
输入格式
第一行包含一个正整数n,含义如题面所示。
输出格式
输出一个整数,代表总和为n 的完全平方数的最少数量。
输入样例
输出样例
18=9+9=16+1+1,其中最少需要2 个完全平方数。

对于全部数据,保证有1≤n≤105。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n;
int dp[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
dp[i]=i;
for(int j=1;j<=sqrt(i);j++){
dp[i] =min(dp[i-j*j]+1,dp[i]);
}
}
cout<<dp[n]<<"\n";
}</pre><p><br/></p>
解析
题目大意:给定一个正整数n,将其拆分成若干个完全平方数的和,要求拆分的数量越少越好。求最少需要多少个完全平方数才能构成n。
用DP进行求解
状态定义
设dp[i]表示构成整数i的最少完全平方数的数量。
状态转移方程
考虑如何通过已知的dp[j](其中j < i)来推导出dp[i]。
对于任意一个整数i,我们可以考虑将它拆分成一个完全平方数j2加上剩余部分i - j2 的和。因此,
dp[i]可以通过dp[i - j2] 来推导出来,即:
dp[i] =min 1≤ k ≤ i (dp[ i−j 2 ]+1)
解释:
dp[i - j2] 表示剩余部分 i - j2 的最少完全平方数数量。+ 1 表示当前添加了一个完全平方数 j2。
我们需要取所有可能的 j 的最小值,以确保 dp[i] 最小。