[LeetCode]Remove Boxes

这道题不难想到应该用DP的思路，但是这算是比较难的DP题目了，难点主要在于我们不好定义这个子问题。一般来讲我们会用dp[i][j]l来定义子区间[i , j]上的子问题，对于这一题来说，如果我们用dp[i][j]表示子区间[i, j]remove boxes之后可以得到的最多分数，这个不是一个独立的子问题，因为最大值还取决于[i, j]区间左边和右边的数字，因为可能会连成更长的连续区间从而得到更多的分数。比如说对于数组A = {3, 3, 2, 3, 2, 4}，对于区间[2, 5] = {2, 3, 2, 4}，我们可能先考虑remove 3从而得到连续的两个2。但实际上如果扩大到整个区间，区间的左边还有两个连续的3，如果我们先remove位于A[0]的2，我们可以得到更多的分数，也就是说我们没有办法从子问题的最优解得到全局最优解。既然单纯的i和j不行，我们需要增加更多的维度来找到独立的子问题。如果我们用dp[i][j][k]表示，对于区间[i, j]的箱子，左边有k个和A[i]相同颜色的箱子的情况下，我们可以得到的最多分数，那么我们可以找到递推公式：

• dp[i][j][k] = max((k +1)^2 * dp[i + 1][j][0], max(dp[i + 1][r - 1][0] + dp[r][j][k + 1])), where A[r] == A[i] && i < r <= j

上面的两项分别对应两种情况：

• 我们首先可以把A[i]和前面k个相同的元素直接抹掉，得到(k + 1)^2分，之后k变为0，我们再继续计算dp[i + 1][j][0]
• A[i +1 : j]中存在和A[i]相同的数假设坐标为r，所以我们也可以选择先remove A[i +1 : r - 1]，这样我们可以把前面的k + 1个相同的数和A[r]连起来，从而继续计算dp[r][j][k + 1]

这个DP方程可以保证我们子问题的最优解可以推广到全局，最后我们要求的就是dp[0][len - 1][0]，时间复杂度，空间复杂度均为O(n^3)，代码如下：