# LeetCode279. Perfect Squares（动态规划）

## LeetCode279. Perfect Squares（动态规划）

• Medium
• Accepted：169,699
• Submissions：411,368

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.

### 链接

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

### 题解

dp[0] = 0
dp[1] = dp[1] + 1 = 1
dp[2] = dp[1] + 1 = 2
dp[3] = dp[2] + 1 = 3
dp[4] = min{dp[4-1*1] + 1, dp[4-2*2] + 1}
= min{dp[3] + 1, dp[0] + 1}
= min{4, 1}
= 1
dp[5] = min{dp[5-1*1] + 1, dp[5-2*2] + 1}
= min{dp[4] + 1, dp[1] + 1}
= min{2, 2}
= 2
......
dp[n] = min{dp[n-i*i] + 1} i >= 1 & n-i*i > 0

#### 代码

• Runtime: 148 ms, faster than 30.79% of C++ online submissions for Perfect Squares.
• Memory Usage: 11.3 MB, less than 49.24% of C++ online submissions for Perfect Squares.
class Solution {
public:
int numSquares(int n) {
vector <int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j * j <= i; ++j)
dp[i] = min(dp[i - j*j] + 1, dp[i]);
return dp[n];
}
};

The end.
2019年3月31日 星期日