真题解析

解析：

题目大意：给定一个正整数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] 最小。

参考程序