1
class Solution {
2
  public int numSquares(int n) {
3
    int dp[] = new int[n + 1];
4
    dp[0] = 0;
5
    dp[1] = 1;
6

7
    for (int i = 2; i < dp.length; i++) {
8
      int min = Integer.MAX_VALUE;
9
      for (int j = 1; j * j <= i; j++) {
10
        min = Math.min(min, dp[i - j * j]);
11
      }
12
      dp[i] = min + 1;
13
    }
14
    return dp[n];
15
  }
16
}