Java DP O(n^(3/2)) solution


  • 0
    M
    	public int numSquares(int n) {
    		if (n <= 0)
    			return 0;
    		int[] dp = new int[n + 1];
    		dp[1] = 1;
    		// j is index between 1 and i; l = j*j; l+r=i.
    		int l = 1, j = 1, r = n - 1, min = n, root = 0;
    		for (int i = 2; i <= n; i++) {
    			root = (int) Math.sqrt(i);
    			if (root * root == i) {
    				dp[i] = 1;
    			} else {
    				j = 1; l = 1; r = i - 1; min = n;
    				while (r > 0) {
    					min = Math.min(min, dp[l] + dp[r]);
    					j++;
    					l = j * j;
    					r = i - l;
    				}
    				dp[i] = min;
    			}
    		}
    		return dp[n];
    	}
    

Log in to reply
 

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