易列出状态转移方程 $dp[i] = min(dp[i], dp[i - j * j] + 1)$ 。

解释：

状态转移方程的含义： 状态转移方程 $dp[i] = min(dp[i], dp[i - j * j] + 1)$（其中 $j * j <= i$ ）的含义是在计算总和为 $i$ 的完全平方数的最小数量 $dp[i]$ 时，考虑使用小于等于 $i$ 的完全平方数 $j * j$ 来构建 $i$ 。 $dp[i - j * j]$ 表示已经计算出的总和为 $i - j * j$ 的完全平方数的最小数量。通过加上一个完全平方数 $j * j$ ，就可以得到总和为 $i$ 的一种拆分方式，其数量为 $dp[i - j * j] + 1$（因为多使用了一个完全平方数 $j * j$ ）。 对于每个 $i$，我们尝试所有可能的完全平方数 $j * j$（只要 $j * j \le i$ ），并从这些可能的拆分方式中选择数量最少的，即取 $min(dp[i], dp[i - j * j] + 1)$ 。这样不断更新 $dp[i]$ ，最终得到总和为 $i$ 的完全平方数的最小数量。

例如，当计算 dp[5] 时： 首先 j = 1，j * j = 1，dp[5 - 1] = dp[4]，假设 dp[4] 之前已经计算为 1（因为 4 = 4 本身就是一个完全平方数，数量为 1），那么 dp[5] 就会更新为 min(dp[5], dp[4] + 1) = min(初始值, 1 + 1) = 2。 然后 j = 2，j * j = 4，dp[5 - 4] = dp[1]，dp[1] 初始为 1（因为 1 = 1），此时 dp[5] 会再次更新为 min(dp[5], dp[1] + 1) = min(2, 1 + 1) = 2（因为 2 更小）。 继续 j = 3，j * j = 9，但 9 > 5，循环结束，dp[5] 最终为 2，表示 5 可以拆分为 1 + 4，使用了两个完全平方数，这是最少的拆分数量。

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    int dp[n + 1];
    for (int i = 0; i <= n; i++) {
        dp[i] = i;  // 初始化，最坏情况就是全是1相加
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }
    cout << dp[n] << endl;
    return 0;
}