顿搜
飞过闲红千叶，夕岸在哪
类目归类
[LeetCode 279] Perfect Squares [Java]
10/16
1. Description
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
2. Runtime Distribution
3. Submission Details
4. Example
given n = 12, return 3 because 12 = 4 + 4 + 4;
given n = 13, return 2 because 13 = 4 + 9.
5. Code
import java.util.Arrays;
public class LeetCode0279 {
public int numSquares(int n) {
if (n <= 0) {
return 0;
}
int m = (int) Math.sqrt(n);
long[] dp = new long[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i < dp.length; i++) {
for (int j = 1; j <= m; j++) {
int num = j * j;
if (i + num <= n) {
dp[i + num] = Math.min(dp[i + num], dp[i] + 1);
}
}
}
return (int) dp[n];
}
public static void main(String[] args) {
LeetCode0279 leetcode = new LeetCode0279();
System.out.println(leetcode.numSquares(13));
}
}
