My Java DP Solution


  • 1
    B

    I camp up with a DP solution in Java.

    DP Solution (33ms)

    public int numSquares(int n) {
                    int state[] = new int [n+1];
    		int temp = 0;
    		int maxSquare = (int) Math.sqrt(n);
    		int positive;
    		state[0] = 1;
    		for(int i=0;i<=n;i++){
    			state[i] = Integer.MAX_VALUE;
    		}
    		for(int i=0;i<=maxSquare;i++){
    			state [i*i] = 1; 
    		}
    		
    		for(int i=1;i<=maxSquare;i++){
    			positive = i*i;
    			for(int j=positive;j<=n-positive;j++){
    				if (state[j]+state[positive]
                                                      <state[j+positive]) {
    					state[j+positive] 
                                                        = state[j]+state[positive];     
    				}
    			}
    		}
    		return state[n];
        }
    

  • 0
    O

    @birdhkl Very clever solution, can you share a little bit how you come up with such a solution? thx


Log in to reply
 

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