leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0279.cpp (426B)

      1 class Solution {
      2   public:
      3     int numSquares(int n) {
      4         vector<int> dp(n + 1, INT_MAX - 1);
      5         vector<int> primes;
      6 
      7         for (int i = 1; i <= sqrt(n); i++)
      8             primes.push_back(i * i);
      9 
     10         dp[0] = 0;
     11         for (int i = 1; i <= n; i++)
     12             for (int j = 0; j < primes.size() && primes[j] <= i; j++)
     13                 dp[i] = min(dp[i], dp[i - primes[j]] + 1);
     14 
     15         return dp[n];
     16     }
     17 };