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

1.比如说f[14] = f[9] + f[4] + f[1] = 3

f[9] = 1 故 f[14] = 1 + f[14 - 9] = 1 + f[5] = 1 + f[4] + f[1]

可以得到f[n] = f[n - j * j] + 1这个状态

又例如f[13] = f[9] + f[4] = 2

初始化所有值为很大的正数 因为要取min 如果设为0就会一直取0

初始化f[0] = 0

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 10010;
int f[N];
int main() {
    int n;
    cin >> n;
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for(int i = 1; i * i <= n; i ++){
        for(int j = i * i; j <= n; j ++){
            f[j] = min(f[j], 1 + f[j - i * i]);

        }
    }
    cout << f[n] << endl;
    return 0;
}