Perfect Squares

Perfect Squares

Description:

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

Example:

Given n = 12, return 3 because 12 = 4 + 4 + 4
Given n = 13, return 2 because 13 = 4 + 9

分析：

动态规划。

假设dp[i]表示当n = i时的最小数，sqrNum存储的是所有不大于n的perfect square number。则对于i以及sqrNum中的数sqrNum[j]

  • 如果i > sqrNum[j]，有状态转移方程dp[i] = min(dp[i], dp[i - sqrNum[j]] + dp[sqrNum[j]])。
  • 如果i == sqrNum[j]，有状态转移方程dp[i] = 1。

不过时间复杂度是O(nlogn)，应该还可以优化。

Code：

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
class Solution {
public:
    /**
     * @param n a positive integer
     * @return an integer
     */
    int numSquares(int n) {
        // Write your code here
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 1;
        dp[1] = 1;
        vector<int> sqrNum;

        for (int i = 0; i <= n; i++) {
            if (pow(i, 2) <= n) sqrNum.push_back(pow(i, 2));
            else break;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = sqrNum.size() - 1; j >= 0; j--) {
                if (i == sqrNum[j]) dp[i] = 1;
                if (i > sqrNum[j]) {
                    dp[i] = min(dp[i], dp[i - sqrNum[j]] + dp[sqrNum[j]]);
                }
            }
        }

        return dp[n];
    }
};