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

思路

这题一看就是一道 $dp$ 题， $dp_i$ 表示组成数字 $i$ 所需的最小平方数数量也就是题意。

初始状态

$dp_0$ 设为 $0$ ，因为 $0$ 只需要 $0$ 个完全平方数。

状态转移

对于每个数字 $i$ 从 $1$ 到 $n$ ，每个数尝试所有 $j \times j$ ， $j$ 是从 $1$ 开始的整数直到 $\sqrt{i}$ ，然后更新 $dp_i$ 。

代码

#include<bits/stdc++.h>//万能头
using namespace std;
// dp[i] 表示组成 i 所需的完全平方数的最小数量
int dp[100005];
int main() {
    int n;
    cin >> n; // 输入正整数 n
    memset(dp,0x7f,sizeof(dp));//全都初始化成大数，方便时候用min
    dp[0]=0; // 0 可以由 0 个完全平方数组成

    // 动态规划计算最小数量
    for (int i=1;i<n;i++) {
        for (int j=1;j*j<=i;j++) { // 计算所有 j*j 使得 j*j<=i
            dp[i] min(dp[i],dp[i-j*j]+1);
        }
    }
    // 输出结果
    cout<<dp[n]<<endl;
    return 0;
}