279. Perfect Squares

T: O(sqrt(n)*n). , because we have n memo, search on this memo,

and for loop is sqrt(n)

```java
class Solution {
    public int numSquares(int n) {
        Integer[] memo = new Integer[n+1];
        List<Integer> candidate = new ArrayList<>();
        for (int i = 1; i*i <= n; i++) { // calculate candidates(perfect squares) first
            candidate.add(i*i);
            memo[i*i] = 1; // complete by itself
        }
        memo[0] = 0;
        dfs(n, candidate, memo);
        return memo[n];
    }
    private int dfs(int n, List<Integer> candidate, Integer[] memo) {
        if (n == 0 || memo[n] != null) {
            return memo[n];
        }
        int result = Integer.MAX_VALUE;
        for (int i = candidate.size()-1; i >= 0; i--) { // like sort, use larger one to substract , more efficient
            int c = candidate.get(i);
            if (n - c >= 0) {
                result = Math.min(result, dfs(n - c, candidate, memo)+1);
            }
        }
        return memo[n] = result;
    }
}

/*

base case: target == 0

count = dfs(target - i*i) + 1

    12
    /\|\\
   1 4 9 
   /. 
  11.    8.        3
  /     7 4 x 
1 4 9

10 7 2
you can see 7 has duplicate cases

  this can do the memo

  T 

why can memo? there are many duplicate case
  dfs(12) = dfs(8) + 1

*/
```