leetcode

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

0343.cpp (485B)

      1 // DP
      2 class Solution {
      3     static int dp[64];
      4 
      5     int rec(const int n) const {
      6         if (n <= 3) return n;
      7         if (dp[n] != -1) return dp[n];
      8         int res = n;
      9         for (int i = 2; i < n; i++)
     10             res = max(res, i * rec(n - i));
     11         return dp[n] = res;
     12     }
     13 
     14   public:
     15     Solution() { memset(dp, 0xFF, sizeof(dp)); }
     16     int integerBreak(const int n) const {
     17         if (n <= 3) return n - 1;
     18         return rec(n);
     19         ;
     20     }
     21 };
     22 
     23 int Solution::dp[64];