题解：P11246 [GESP202409 六级] 小杨和整数拆分

easy42 · 2024-11-04 17:46:50 · 题解

清新的动态规划。

易列出状态转移方程 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 <= 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;
}

可以的话，能不能点个关注和赞？