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

对于全部数据,保证有1≤n≤105。
答案与解析
正确答案:<pre class="brush:python;toolbar:false">import math
N = int(1e5) + 10
dp = [0] * N
n = int(input())
for i in range(1, n + 1):
dp[i] = i
for j in range(1, int(math.sqrt(i)) + 1):
dp[i] = min(dp[i - j * j] + 1, dp[i])
print(dp[n])</pre>
解析
题目大意:给定一个正整数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] 最小。