leetcode

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

0546.cpp (804B)

      1 class Solution {
      2     static int dp[200][200][200];
      3 
      4     static int rec(const vector<int> &boxes, int l, int r, int k) {
      5         if (l > r) return 0;
      6         if (dp[l][r][k] > 0) return dp[l][r][k];
      7 
      8         int lOrg = l, kOrg = k;
      9         while (l + 1 <= r && boxes[l] == boxes[l + 1])
     10             l += 1, k += 1;
     11 
     12         int ans = (k + 1) * (k + 1) + rec(boxes, l + 1, r, 0);
     13         for (int m = l + 1; m <= r; ++m) {
     14             if (boxes[m] != boxes[l]) continue;
     15             ans = max(ans, rec(boxes, m, r, k + 1) + rec(boxes, l + 1, m - 1, 0));
     16         }
     17         return dp[lOrg][r][kOrg] = ans;
     18     }
     19 
     20   public:
     21     int removeBoxes(const vector<int> &boxes) const {
     22         memset(dp, 0x00, sizeof(dp));
     23         return rec(boxes, 0, size(boxes) - 1, 0);
     24     }
     25 };
     26 
     27 int Solution::dp[200][200][200];