- Difficulty: Medium
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
.public class Solution { public int numSquares(int n) { //dp[n] = Min{ dp[n - i*i] + 1 }, n - i*i >=0 && i >= 1 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]; } }
No comments:
Post a Comment