题解 | 最少的完全平方数

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e4 + 5;
int dp[MAXN];
signed main()
{
    int n;cin >> n;
    memset(dp, 0x1f, sizeof(dp));//要求最小值就初始化为较大的数
    dp[0] = 0;//1.0的完全平方数和为0 2.是为了后续求dp[i]时能知道是否可以组成n
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1;j*j <= i; j++)//枚举j的平方的范围
        {
            dp[i] = min(dp[i],dp[i-j*j]+1);//当前数i减去j的平方值能组成的最小完全平方数+1
        }
    }
    cout << dp[n] << endl;
    return 0;
}