【LeetCode】移除盒子 [H]（记忆化搜索）

546. 移除盒子 - 力扣（LeetCode）

一、题目

给出一些不同颜色的盒子 boxes ，盒子的颜色由不同的正数表示。

你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k * k 个积分。

返回 你能获得的最大积分和 。

示例 1：
输入：boxes = [1,3,2,2,2,3,4,3,1]
输出：23
解释：
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 分) 
----> [1, 3, 3, 3, 1] (1*1=1 分) 
----> [1, 1] (3*3=9 分) 
----> [] (2*2=4 分)

示例 2：
输入：boxes = [1,1,1]
输出：9

示例 3：
输入：boxes = [1]
输出：1

提示：

• 1 <= boxes.length <= 100
• 1 <= boxes[i] <= 100

二、代码

class Solution {
    public int removeBoxes(int[] boxes) {
        int n = boxes.length;
        if (n == 1) {
            return 1;
        }
 
        int[][][] dp = new int[n][n][n];
        return process(boxes, 0, n - 1, 0, dp);
    }
 
    // arr[L...R]消除，而且前面跟着K个boxes[L]这个数
	// 返回：所有东西都消掉，最大得分
    public int process(int[] boxes, int l, int r, int k, int[][][] dp) {
        if (l > r) {
            return 0;
        }
 
        if (dp[l][r][k] != 0) {
            return dp[l][r][k];
        }
 
        // 常数优化点
        // 找到l+1~r范围上前面连续等于boxes[l]的最后的位置
        int last = l;
        for (int i = l + 1; i <= r; i++) {
            if (boxes[i] != boxes[i - 1]) {
                break;
            }
            last++;
        }
 
        // 统计算上l前面的k个boxes[l]，再加上l+1~r的连续等于boxes[l]的最长前缀的个数，算一共有多少个连续前缀boxes[l]。注意这里没有算l位置的这个数，后面要自己加1
        int pre = k + (last - l);
 
        // 选择一：将l前面k个boxes[l]和l~last的连续的boxes[l]合并，得分是(pre + 1) * (pre + 1)
        // 然后将后面的last+1~r范围的数自己合并，递归调用为process(boxes, last + 1, r, 0, dp)
        int p1 = (pre + 1) * (pre + 1) + process(boxes, last + 1, r, 0, dp);
 
        // 选择二：将lasr+1~i-1范围内的数自己区合并，递归调用为process(boxes, last + 1, i - 1, 0, dp)
        // 当lasr+1~i-1范围合并全都消掉之后，last+1前面的连续相同的pre+1个boxes[l]就和i~r范围的数相邻了，然后就将这两个分去合并消除，递归调用为process(boxes, i, r, pre + 1, dp)
        int p2 = Integer.MIN_VALUE;
        // 尝试所有符合要求的i位置，来找到所有可能情况的最大得分
        for (int i = last + 1; i <= r; i++) {
            int temp = 0;
            if (boxes[i] == boxes[l]) {
                temp = process(boxes, last + 1, i - 1, 0, dp) + process(boxes, i, r, pre + 1, dp);
            }
            p2 = Math.max(p2, temp);
        }
 
        /**
            这两种选择就是以前面连续相同的boxes[l]作为基准，要么就前缀连续相同的数自己合并，再将剩下部分自己合并
            要么将整个范围中间的部分去合并消除，中间消除之后再将两边部分的数在一起合并消除
            这两种选择就可以将所有可能的情况都涵盖了，不会漏掉
         */
 
        dp[l][r][k] = Math.max(p1, p2);
        return dp[l][r][k];
    }
}

三、解题思路 

采用记忆化搜索的思路，关键是如何建立递归模型。