简答题 偏难
#20888

小杨和整数拆分 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有一个正整数n,小杨想将它拆分成若干完全平方数的和,同时小杨希望拆分的数量越少越…

小杨和整数拆分

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一个正整数n,小杨想将它拆分成若干完全平方数的和,同时小杨希望拆分的数量越少越好。

小杨请你编写程序计算出总和为n 的完全平方数的最少数量。

输入格式

第一行包含一个正整数n,含义如题面所示。

输出格式

输出一个整数,代表总和为n 的完全平方数的最少数量。

输入样例

18

输出样例

2

18=9+9=16+1+1,其中最少需要2 个完全平方数。

对于全部数据,保证有1≤n≤105。


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int N = 1e5+10; int n; int dp[N]; int main(){ cin&gt;&gt;n; for(int i=1;i&lt;=n;i++){ dp[i]=i; for(int j=1;j&lt;=sqrt(i);j++){ dp[i] =min(dp[i-j*j]+1,dp[i]); } } cout&lt;&lt;dp[n]&lt;&lt;"\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] 最小。