1
class Solution {
2
 public:
3
  int numSquares(int n) {
4
    vector<int> perfectSq;
5

6
    for (int i = 1; i * i <= n; ++i) {
7
      perfectSq.push_back(i * i);
8
    }
9

10
    int m = perfectSq.size();
11
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
12

13
    dp[0][0] = 0;
14
    for (int i = 1; i <= n; ++i) dp[0][i] = INT_MAX;
15

16
    for (int i = 1; i <= m; ++i) {
17
      for (int j = 1; j <= n; ++j) {
18
        if (j < perfectSq[i - 1]) {
19
          dp[i][j] = dp[i - 1][j];
20
        } else {
21
          dp[i][j] = min(dp[i - 1][j], dp[i][j - perfectSq[i - 1]] + 1);
22
        }
23
      }
24
    }
25

26
    return dp[m][n];
27
  }
28
};