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.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
The idea using DP is simple, For a number N, if some int i*i = N, then dp[N] = 1;
else for every k from 1 -> n - 1 dp[N] = min(dp[k] + dp[n-k]);
Code:
public class Solution { public int numSquares(int n) { int[] dp = new int[n + 1]; int i = 0; while(i*i <= n){ dp[i*i] = 1; i++; } for(i = 2; i < dp.length; i++){ if(dp[i] == 0){ int temp = Integer.MAX_VALUE; for(int k = 1; k < i; k++){ temp = Math.min(temp,dp[k] + dp[i - k]); } dp[i] = temp; } } return dp[n]; } }However, this gets TLE, since it actually requires O(N2) time.How to optimize, for example 12 = 4 + 4 + 4, we get 12 = 1 + 11, 2 + 10 3 + 9....., which is unnecessary.
for 2 + 10 , it actually the same with 1 + 11, because they all will get factor 1,
So what we could do is to pick k that is the square of some int.
public class Solution { public int numSquares(int n) { int[] dp = new int[n + 1]; int i = 0; while(i*i <= n){ dp[i*i] = 1; i++; } for(i = 2; i < dp.length; i++){ if(dp[i] == 0){ int temp = Integer.MAX_VALUE; for(int k = 1; k * k < i; k++){ temp = Math.min(temp,1 + dp[i - k*k]); } dp[i] = temp; } } return dp[n]; } }
