3503.小杨和整数拆分

题目分析

题目要求将一个正整数 ( n ) 拆分成若干个完全平方数（如 ( 1,4,9,16,\dots )）的和，且希望使用的完全平方数的个数最少。例如 ( n = 12 ) 时，可以拆成 ( 4 + 4 + 4 )（3个数），也可以拆成 ( 9 + 1 + 1 + 1 )（4个数），但不难找到更优的方案 ( 4 + 4 + 4 ) 或 ( 9 + 1 + 1 + 1 ) — 实际上 12 最少需要 3 个平方数。本题就是求对于给定的 ( n )，最少需要多少个完全平方数。

解题思路

这是一个典型的动态规划问题。

定义：

• ( dp[i] ) 表示将正整数 ( i ) 拆分成完全平方数之和所需要的最少个数。

边界条件：

• ( dp[0] = 0 )，因为和为 0 不需要任何数。
• 对于任意 ( i \ge 1 )，最坏情况是全部拆成 1，需要 ( i ) 个数，所以可将 ( dp[i] ) 初始化为 ( i )。

状态转移：

• 考虑最后一个完全平方数 ( j^2 )，只要 ( j^2 \le i )，我们就可以从 ( dp[i - j^2] ) 转移过来，加上这一个数 ( j^2 ) 即可。
• 因此转移方程为：
  [
  dp[i] = \min_{1 \le j \le \lfloor\sqrt{i}\rfloor} { dp[i - j^2] + 1 }
  ]

最终答案即为 ( dp[n] )。

算法说明

1. 读入 ( n )，创建一个长度为 ( n+1 ) 的数组 ( dp )。
2. 初始化 ( dp[0] = 0 )，对于 ( i ) 从 ( 1 ) 到 ( n )，先将 ( dp[i] ) 赋为 ( i )（全用 1 的情况）。
3. 用两重循环更新：
   • 外层循环 ( i ) 从 ( 1 ) 到 ( n )，计算每个 ( dp[i] )。
   • 内层循环 ( j ) 从 ( 1 ) 开始，直到 ( j^2 \le i )，尝试用 ( dp[i - j^2] + 1 ) 更新 ( dp[i] )。
4. 输出 ( dp[n] )。

由于计算 ( dp[i] ) 时，所依赖的状态 ( dp[i - j^2] ) 一定比 ( i ) 小，因此按 ( i ) 从小到大的顺序递推是正确的。

时间复杂度分析

• 外层循环遍历 ( i = 1 \sim n )，共 ( n ) 次。
• 内层循环枚举 ( j )，约 ( \sqrt{i} ) 次，最大为 ( \sqrt{n} )。
• 总时间复杂度为 ( \sum_{i=1}^{n} \sqrt{i} \approx O(n \sqrt{n}) )。
• 对于 ( n \le 10^5 )，( n \sqrt{n} \approx 10^5 \times 316 = 3.16 \times 10^7 )，在 1 秒内完全可以运行通过。

空间复杂度为 ( O(n) )，存储 ( dp ) 数组。

代码实现

参考代码与上述思路完全一致，下面给出带有详细注释的版本：

cpp
复制
1#include <iostream>
2#include <cmath>
3using namespace std;
4
5int main() {
6    int n;
7    cin >> n;
8
9    // dp[i] 表示 i 最少由几个完全平方数组成
10    int dp[n + 1];
11    
12    // 初始化
13    dp[0] = 0;          // 和为0需要0个数
14    for (int i = 1; i <= n; i++) {
15        dp[i] = i;      // 最坏情况：全用 1 相加
16    }
17
18    // 动态规划
19    for (int i = 1; i <= n; i++) {
20        // 枚举最后一个完全平方数 j*j
21        for (int j = 1; j * j <= i; j++) {
22            // 状态转移：从 i - j*j 的方案再加上一个 j*j
23            dp[i] = min(dp[i], dp[i - j * j] + 1);
24        }
25    }
26
27    // 输出结果
28    cout << dp[n] << endl;
29    return 0;
30}

代码解释：

• dp[i] = i 是一种简单的上界初始值，因为我们总可以用 ( i ) 个 ( 1^2 ) 相加得到 ( i )。
• 内层循环中 j * j <= i 保证了枚举的平方数不超过当前数。
• min(dp[i], dp[i - j * j] + 1) 表示若最后一个平方数是 ( j^2 )，那么剩下的 ( i - j^2 ) 需要的最小个数加上 1，即为新的可能答案，我们取最小值。
• 最终 dp[n] 就是我们要求的最小数量。

总结

本题是完全背包问题的一个变形，使用动态规划可以高效求解。关键点在于正确设计状态和转移方程，并注意初始化和枚举顺序。掌握这种方法后，类似“将一个数拆分成某种特定数字的和，求最少个数”的题目都可以用同一种思路解决。