LeetCode 279 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.
Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 4 4.
Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 9.
翻译过来就是给定一个数，找到一组完全平方数，其和等于给定的数。而且要求这一组完全平方数的个数最少。
2. 思路
- 定义dp[] 数组，dp[i]表示 给定i时perfect square 的数目。
- dp[0] = 0
- dp[1] = dp[0] 1
- dp[2] = dp[1] 1
- dp[3] = dp[2] 1
- dp[4] = Min{dp[4 - 1 * 1] 1 , dp[4 - 2 * 2] 1} = 1
- dp[5] = Min{dp[5 - 1 * 1] 1, dp[5 - 2 * 2] 1} = 2
- dp[n] = Min{dp[n - 1 * 1] 1, dp[n - 2 * 2] 1, ...}
3. 代码
代码语言：javascript复制class Solution {
public int numSquares(int n) {
int[] dp = new int[n 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1; i <= n; i) {
int min = Integer.MAX_VALUE;
int j = 1;
while(i - j * j >= 0) {
min = Math.min(min, dp[i - j * j] 1);
j;
}
dp[i] = min;
}
return dp[n];
}
}
