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

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
const int M = 1e4 + 10;
int a[N], f[M], n;
int main()
{
    cin >> n;
    for (int i = 0; i < N; i++) {
        a[i] = i * i;
    }
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i < N; i++) {
        for (int j = a[i]; j <= n; j++) {
            f[j] = min(f[j], f[j - a[i]] + 1);
        }
    }
    cout << f[n] << endl;
    return 0;
}