# Java DP straightforward solution with detailed comments : 58ms

• ``````public class PerfectSquares {

private int[] memo = null;

/**
* Algorithm is as follows.
* Given N, attempt to calculate all possible scenarios by subtracting largest
*  possible squared number to smallest, call this value L, and repeat the process
*  on N-L. On each attempt,save the current steps if better solution is
*  found and do not process if better solution is already found.
*
* memo array keeps track of steps to taken to get to n by subtracting possible
*  squared number that's less than N. (e.g. memo[3] = minimum steps taken for
*  N to get to 3) Because of this property memo[0] will be steps taken for N to
*  get to 0, which is the answer we are interested in.
*
* @param n
* @return
*/
public int numSquares(int n) {

// Integer.MAX_VALUE means not solved yet.
memo = new int[n+1];
for(int i = 0; i < memo.length; i++) {
memo[i] = Integer.MAX_VALUE;
}

findMinSquare(n, 0);

return memo[0];
}

private void findMinSquare(int n, int steps) {
/**
* There are two conditions that we know when NOT to proceed further
* 1. Problem is solved previously and has equal or more closer answer
* -----> (memo[n] <= steps)
* 2. Number of steps to get n is equal or less than the minimum that
* -----> (steps >= memo[0])
*/
if(memo[n] <= steps || steps >= memo[0]) {
return;
}

int largestFit = (int) Math.floor(Math.sqrt(n));

/**
* Try different solution. Lesser closer solution will be terminated because
*  of base condition in the method
*
*/
for(int i = largestFit; i >= 1; i--) {
findMinSquare(n - i*i, steps + 1);
}

/**
* Is current number of steps smaller than previously calculated steps?
* - If yes, then we memo it
*
*/
if(memo[n] > steps) {
memo[n] = steps;
}
}
}``````

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