LeetCode p279 Perfect Squares 题解
1.题目：
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, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
题意：
找出一个数最少由多少个完全平方数组成。
2.解题思路:
dp
3.代码
[title] [] [url] [link text]
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
|
public class {
public int min = Integer.MAX_VALUE;
public int numSquares(int n) {
dp(n, 0);
return min;
}
public void dp(int n, int count) {
if (count >= min)
return;
int c = (int) Math.sqrt(n);
if (c * c == n) {
min = Math.min(count + 1, min);
}
if (c == 1) {
min = Math.min(count + n, min);
}
for (int i = c; i > 0; i--) {
dp(n - i * i, count + 1);
}
}
}
|
4.一些总结：
近期评论