My Java DP Solution

  • 1

    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]+state[positive];     
    		return state[n];

  • 0

    @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.