题目描述

给定一个正整数 n ，找到最少数量的平方数（例如1, 4, 9, 16）使这些平方数的和等于 n 。

返回最少的数量。

样例

Example 1:

Input: n = 12
Output: 3 
解释: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
解释: 13 = 4 + 9.

算法

(动态规划)

C++ 代码

// 2022年2月1日 16:19:17
class Solution {
public:
    int f[107][10007];
    int v[107];
    int numSquares(int n) {
        // 整数划分：完全背包变形 时间复杂度: O(n*sqrt(n))
        int m = (int)sqrt(n);
        for (int i = 1; i <= m; i ++) v[i] = i * i;

        memset(f, 0x3f, sizeof(f));
        f[0][0] = 0;

        for (int i = 1; i <= m; i ++) {
            for (int j = 0; j <= n; j ++) {
                f[i][j] = min(f[i][j], f[i - 1][j]);
                if (j >= v[i]) f[i][j] = min(f[i][j], f[i][j - v[i]] + 1);
            }
        }
        return f[m][n];
    }
};

class Solution {
public:
    int numSquares(int n) {
        vector <int> f(n + 1, 0x3f3f3f3f);
        f[0] = 0;
        for (int i = 1; i <= n; i++) { 
            for (int j = 1; j * j <= i; j++) { 
                f[i] = min(f[i], f[i - j * j] + 1);
            }
        }
        return f[n];
}