279. Perfect Squares

问题

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

例子

given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

分析

• 方法一：静态的动态规划。静态状态表可以在所有case中共有，因此可以大大地提高效率（比一般的动态规划快几十倍）；
• 方法二：数学方法。详见Lagrange's four-square theorem.
• 方法三：bfs.

要点

static dynamic programming

时间复杂度

• 方法一：O(n^2)
• 方法二：O(O^0.5)

空间复杂度

• 方法一：O(n)
• 方法二：O(1)

代码

方法一

class Solution {
public:
    int numSquares(int n) {
        static vector<int> dp({0});
        while (dp.size() <= n) {
            int curNumSquares = INT_MAX;
            for (int i = 1; i * i <= dp.size(); i++) {
                curNumSquares = min(curNumSquares, dp[dp.size() - i * i] + 1);
            }
            dp.push_back(curNumSquares);
        }
        return dp[n];
    }
};

方法二

class Solution {
public:
    int numSquares(int n) {
        while (n % 4 == 0)
            n /= 4;
        if (n % 8 == 7)
            return 4;
        for (int a=0; a*a <= n; ++a) {
            int b = sqrt(n - a*a);
            if (a*a + b*b == n)
                return 1 + !!a;
        }
        return 3;
    }
};