p279

发表于 | 分类于 |

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 Solution {
    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.一些总结：