Java实现 LeetCode 546 移除盒子（递归，vivo秋招）

素颜马尾好姑娘i 2023-07-18 09:15 13阅读 0赞

## 546. 移除盒子 ##

给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。  
你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k\*k 个积分。  
当你将所有盒子都去掉之后，求你能获得的最大积分和。

示例 1：  
输入:

\[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 分)

提示：盒子的总数 n 不会超过 100。

PS：

## `网友大哥：2019.9.11 vivo秋招， 数据分析， 第三题原题， 多么痛的领悟` ##

class Solution { 
        public int removeBoxes(int[] boxes) {   
            int[][][] scores = new int[boxes.length][boxes.length][boxes.length];
    
            return calcMaxScore(boxes, 0, boxes.length - 1, 0, scores);
        }
    
        private int calcMaxScore(int[] boxes, int left, int right, int sameCount, int[][][] scores) { 
            if (left > right) { 
                return 0;
            }
    
            int maxScore = scores[left][right][sameCount];
            if (maxScore != 0) { 
                return maxScore;
            }
    
            int pos = left - 1;
            for (int i = right - 1; i >= left; --i) { 
                if (boxes[i] != boxes[right]) { 
                    pos = i;
                    break;
                }
            }
            int mergeSameCount = sameCount + right - pos;
            maxScore = calcMaxScore(boxes, left, pos, 0, scores) + mergeSameCount * mergeSameCount;
    
            for (int i = pos - 1; i >= left; --i) { 
                if (boxes[i] == boxes[right] && boxes[i + 1] != boxes[right]) { 
                    int score = calcMaxScore(boxes, left, i, mergeSameCount, scores) + calcMaxScore(boxes, i + 1, pos, 0, scores);
                    maxScore = Math.max(maxScore, score);
                }
            }
    
            scores[left][right][sameCount] = maxScore;
    
            return maxScore;
        }
    }