leetcode Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example,
1, 4, 9, 16, ...
) which sum to n.For example, given n =
12
, return3
because12 = 4 + 4 + 4
; given n =13
, return2
because13 = 4 + 9
.
题目地址: leetcode Perfect Squares
题意: 给定一个整数n,找到最少的完全平方数使得他们的和为n
思路:
dp,设dp[i]为和i的最少完全平方数。
dp[i] = min(dp[i - j*j] + 1) {j *j <i}
code
C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int numSquares(int n) {
int *dp = new int[n + 1];
for (int i = 0; i <= n; i++) {
dp[i] = i;
for (int j = 1; j * j <= i; j++) {
if (dp[i - j*j] + 1 < dp[i])
dp[i] = dp[i - j*j] + 1;
}
}
return dp[n];
}
};
Python同样的代码会超时。。。