279. Perfect Squares

https://leetcode.com/problems/perfect-squares/

Problem

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.

Solution

class Solution {
public:
    int numSquares(int n){
        static vector<int> dp{0};
        static int sqrt = 1;
        while (dp.size() - 1 < n) {
            int i = dp.size();
            if (i == sqrt * sqrt) {
                dp.emplace_back(1);
                ++sqrt; continue;
            }
            int min_count = INT_MAX;
            for (int j = 1; j * j < i; ++j) {
                if (min_count > dp[i - j * j] + dp[j * j]) min_count = dp[i - j * j] + dp[j * j];
            }
            dp.emplace_back(min_count);
        }
        return dp[n];
    }
};

• #dp

• #math

• #important