Leetcode 546


  Posted on 29 Mar 2017
dynamic programming


Tutorial

dp[l][r][k] means the maximum value of interval [l, r] with k repeating characters of boxes[r] at the back after r. The equation is dp(l, r, k) = max(dp(l, i, k + 1) + dp(i + 1, r - 1, 0)) for boxes[i] == boxes[r]. It means we remove [i+1, r - 1] first, and remove the repeating characters at the back with boxes[i] together.

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
	int n;
	vector<int> boxes;
	public:
		int removeBoxes(vector<int>& boxes) {
			int dp[100][100][100];
			memset(dp, -1, sizeof(dp));
			n = boxes.size();
			this->boxes = boxes;
			int ans = dfs(0, n - 1, 0, dp);
			return ans;
		}

		int sqr(int a) {
			return a * a;
		}

		int dfs(int l, int r, int k, int dp[100][100][100]) {
			if (l > r) {
				return 0;
			}

			if (dp[l][r][k] != -1) {
				return dp[l][r][k];
			}

			int ret = 0;
			if (r - 1 >= 0 && boxes[r - 1] == boxes[r]) {
				ret = dfs(l, r - 1, k + 1, dp);
				dp[l][r][k] = ret;
				return ret;
			}
			ret = dfs(l, r - 1, 0, dp) + sqr(k + 1);
			for (int i = l; i < r; i++) {
				if (boxes[i] != boxes[r])
					continue;
				ret = max(ret, dfs(l, i, k + 1, dp) + dfs(i + 1, r - 1, 0, dp));
			}
			dp[l][r][k] = ret;
			//printf("%d %d %d %d\n", l, r, k, ret);
			return ret;
		}
};