leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0279.cpp (426B)

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 };