题解 | #最少的完全平方数#

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010, INF = 0x3f;
int a[N], cnt;
int dp[N], n;
void init()
{
    memset(dp, 0x3f, sizeof dp);
    for(int i = 1; i * i <= n; i ++)
    {
        a[cnt ++] = i * i;
        dp[i * i] = 1;
    }
}
int main() {
    cin >> n;
    init();
    // for(int i = 0; i <= n; i ++) cout << dp[i] << ' ';
    for(int i = 0; i < cnt; i ++)
    {
        int v = a[i];
        for(int j = v; j <= n; j ++)
        {
            dp[j] = min(dp[j], dp[j - v] + 1);
        }
    }
    cout << dp[n];
    return 0;
}
// 64 位输出请用 printf("%lld")