```
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
* we already calculated
* -----> (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;
}
}
}
```