f[i] 表示数字 i 最少可以由几个完全平方数相加构成。在本题中，位置 i 只依赖 i - *k^*2 的位置，如 i - 1、i - 4、i - 9 等等，才能满足完全平方分割的条件。 因此 dp[i] 可以取的最小值即为 1 + min(f[i-1], f[i-4], f[i-9]...)

class Solution {
public:
    int numSquares(int n) {
        int INF = 1e5;
        vector<int> f(n + 1, INF);
        f[0] = 0;
        for (int i = 1; i <= n; i ++) {
		        // f[i] 的取值依赖于之前所有的 f[i - k^2]
            for (int j = 1; j * j <= i; j ++) {
                f[i] = min(f[i], f[i - j * j] + 1);
            }
        }
        return f[n];
    }
};

完全背包

<aside> 💡 我已经忘记了，2023-06-21 22:14:18 要记得回来复习!!

</aside>

class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1, INT_MAX);
        f[0] = 0;
        for (int i = 1; i * i <= n; i ++) { // 遍历物品
            for (int j = i * i; j <= n; j ++) { // 遍历背包容量
                f[j] = min(f[j], f[j - i * i] + 1);
            }
        }
        return f[n];
    }
};

class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1, INT_MAX);
        vector<int> nums;
        for (int i = 1; i <= sqrt(n); i++) {
            nums.push_back(i * i);
        }

        f[0] = 0;
        for (auto x : nums) {
            for (int j = x; j <= n; j++) {
                if (j - x >= 0) f[j] = min(f[j], f[j - x] + 1);
            }
        }
        return f[n];
    }
};