leetcode

0 class Solution {

1 public:

2 int numSquares(int n) {

3 vector<int> dp(n + 1, INT_MAX - 1);

4 vector<int> primes;

5

6 for (int i = 1; i <= sqrt(n); i++)

7 primes.push_back(i * i);

8

9 dp[0] = 0;

10 for (int i = 1; i <= n; i++)

11 for (int j = 0; j < primes.size() && primes[j] <= i; j++)

12 dp[i] = min(dp[i], dp[i - primes[j]] + 1);

13

14 return dp[n];

15 }

16 };