279

279. Perfect Squares (Medium)

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

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Companies:
Lyft, Uber, Google, Adobe, Amazon, Facebook

Related Topics:
Math, Dynamic Programming, Breadth-first Search

Similar Questions:

• Count Primes (Easy)
• Ugly Number II (Medium)

Solution 1. DP Bottom-up

// OJ: https://leetcode.com/problems/perfect-squares/
// Author: github.com/lzl124631x
// Time: O(NS) where S is the count of square numbers less than n.
// Space: O(N)
class Solution {
public:
    int numSquares(int n) {
        vector<int> v(n + 1, INT_MAX);
        for (int i = 1; i * i <= n; ++i) v[i * i] = 1;
        for (int i = 1; i <= n; ++i) {
            if (v[i] == 1) continue;
            for (int j = 1; j * j < i; ++j) {
                v[i] = min(v[i], 1 + v[i - j * j]);
            }
        }
        return v[n];
    }
};

Solution 2. DP Top-down

// OJ: https://leetcode.com/problems/perfect-squares/
// Author: github.com/lzl124631x
// Time: O(NS) where S is the count of square numbers less than n.
// Space: O(N)
class Solution {
    vector<int> memo;
    int dp(int n) {
        if (n == 0) return 0;
        if (memo[n]) return memo[n];
        int ans = INT_MAX;
        for (int i = 1; i * i <= n; ++i) ans = min(ans, 1 + dp(n - i * i));
        return memo[n] = ans;
    }
public:
    int numSquares(int n) {
        memo.assign(n + 1, 0);
        for (int i = 1; i * i <= n; ++i) memo[i * i] = 1;
        return dp(n);
    }
};

Solution 3.

// OJ: https://leetcode.com/problems/perfect-squares/
// Author: github.com/lzl124631x
// Time: O(NS) where S is the count of square numbers less than n.
// Space: O(N)
// Ref: https://discuss.leetcode.com/topic/24255/summary-of-4-different-solutions-bfs-dp-static-dp-and-mathematics
class Solution {
public:
    int numSquares(int n) {
        static vector<int> dp{0};
        while (dp.size() <= n) {
            int m = dp.size(), minVal = INT_MAX;
            for (int i = 1; i * i <= m; ++i) minVal = min(minVal, 1 + dp[m - i * i]);
            dp.push_back(minVal);
        }
        return dp[n];
    }
};