An easy understanding DP solution in Java


  • 164
    K

    dp[n] indicates that the perfect squares count of the given n, and we have:

    dp[0] = 0 
    dp[1] = dp[0]+1 = 1
    dp[2] = dp[1]+1 = 2
    dp[3] = dp[2]+1 = 3
    dp[4] = Min{ dp[4-1*1]+1, dp[4-2*2]+1 } 
          = Min{ dp[3]+1, dp[0]+1 } 
          = 1				
    dp[5] = Min{ dp[5-1*1]+1, dp[5-2*2]+1 } 
          = Min{ dp[4]+1, dp[1]+1 } 
          = 2
    						.
    						.
    						.
    dp[13] = Min{ dp[13-1*1]+1, dp[13-2*2]+1, dp[13-3*3]+1 } 
           = Min{ dp[12]+1, dp[9]+1, dp[4]+1 } 
           = 2
    						.
    						.
    						.
    dp[n] = Min{ dp[n - i*i] + 1 },  n - i*i >=0 && i >= 1
    

    and the sample code is like below:

    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];
    }
    

    Hope it can help to understand the DP solution.


  • 0
    P

    brilliant idea!


  • 0
    Z

    Seems like O(n) space complexity. Is there no way to bring that down? What if n == MAX_INT?


  • 1
    K

    Of course you can just use O(1) space to solve this problem, you can refer to Lagrange's four-square theorem and try to find out a mathematical solution(in fact, there're some leetcoders using this), but in this case, if you insist on using DP to solve it, I don't think you can bring the space complexity down, here dp[n] doens't only depend on dp[n-1], you have to keep { dp[n - ii] + 1 , n - ii >=0 && i >= 1 } until you get the best dp[n].


  • 1
    D

    Can someone help us explain why the complexity is O(n)?
    this is a sum of all square roots from 1 to n .. is this proven to be equivalent to O(n) ?


  • 0
    D

    got that .. just integrate sqrt(n) ~> (n^3/2) .. got confused thinking someone called this solution O(n) ..


  • 5
    Z

    Why do you need Arrays.fill(dp, Integer.MAX_VALUE);? This solution runs just fine without this line.


  • 0

    really nice idea!


  • 0
    C

    Nice solution!

    Also I think Arrays.fill(dp, Integer.MAX_VALUE) isn't necessary here.


  • 0
    A

    What's the time complexity of this method. Very elegant and simple solution. I'm having trouble deriving time complexity. For each value of i, inner loop is running root of i times.
    Ex: for 16 it will run for:
    16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
    4 4 4 4 4 4 4 3 3 3 3 3 2 2 2 1 (something like that)

    Will it still be O(N) as some people have mentioned.


  • 0
    B

    @agrawalm
    as some already said above, I think time complexity is O(n^1.5), space complexity is O(n)


  • 0
    S

    @benqiang
    Actually some of the calculations could be ignored. E.g. if sqrt(n) - (int)sqrt(n) == 0 then we can set the value to 1 directly. If it isn't, then the least numbers should be greater or equal than 2. If ever meet 2, we can set the value to 2 directly.


  • 0

    Thanks for sharing.


  • 1

    @Karci
    simplified solution

    public 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++){
                for(int j = 1; j * j <= i; j++){
                    dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
                }
            }
            return dp[n];
        }
    }
    

  • 0
    M

    Guys, does anyone know what's the time complexity of this solution?
    Thanks a lot!


  • 0
    I

    @Karci Nice solution mate.. Thanks for sharing :)


  • 0
    M

    @MorganZhang1991
    I think it's O(n^3/2)


  • 0
    M

    This is exactly the "Knapsack Problem"


  • 0
    V

    can someone explain the meaning of i-jj ? and why while i-jj >= 0 ?


  • 0

    WHY

            for(int j = 1; j * j <= i; j++)
    

    skip those between j * j ~ (j + 1) * (j + 1) [as gap]

    My solution is like this, trying to figure it out why we could skip the gap

    public int numSquares(int n) {
            int[] res = new int[n + 1];
            Arrays.fill(res, Integer.MAX_VALUE);
            res[0] = 1;
            for (int i = 1; i <= n; i++) {
                int root = (int)Math.sqrt(i);
                if (root * root == i) {
                    res[i] = 1;
                    continue;
                }
                for (int j = 1; j <= i / 2; j++) {
                    // int subroot = (int)Math.sqrt(i - j);
                    // if (subroot * subroot == i - j) {
                    res[i] = Math.min(res[i], res[i - j] + res[j]);
                    // }
                }
                // System.out.println(res[i]);
            }
            return res[n];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.