279. Perfect Squares

Posted on Edited on In

279. Perfect Squares

Description

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= n <= 10^4

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<int> coins;
    vector<int> dp;

    int numSquares(int n) {
        for (int i = 1; i * i <= n; i++) {
            coins.push_back(i * i);
        }
        dp.resize(n + 1, -1);
        int res = dfs(n);
        return res;
    }

    int dfs(int n) {
        if (n == 0) {
            return 0;
        }
        if (dp[n] != -1) {
            return dp[n];
        }
        int res = INT_MAX;
        for (int i = coins.size() - 1; i >= 0; i--) {
            if (coins[i] > n) {
                continue;
            }
            res = min(res, 1 + dfs(n - coins[i]));
        }
        dp[n] = res;
        return res;
    }
};