leetcode

Solution to some Leetcode problems written in C++

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

0546.cpp (804B)

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