<jupyter_start><jupyter_text>说明：    给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。    你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。    每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。    当你将所有盒子都去掉之后，求你能获得的最大积分和。示例：    输入：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 分)提示：    1 <= boxes.length <= 100    1 <= boxes[i] <= 100<jupyter_code>class Solution:
    def removeBoxes(self, boxes) -> int:
        # dp[l][r][k] 表示在 l-r 的区间长度内，在r后面还有 k 个元素 == boxes[r] 
        dp = [[[0] * 100 for _ in range(100)] for _ in range(100)]
        n = len(boxes)
        
        def dfs(l, r, k):
            if l > r: 
                return 0
            if dp[l][r][k] != 0:
                return dp[l][r][k]
            
            idx = r
            count = k
            while idx >= l and boxes[idx] == boxes[r]:
                idx -= 1
                count += 1
                
            # 第一种情况
            dp[l][r][k] = dfs(l, idx, 0) + count * count
            # 第二种情况
            for j in range(idx, l-1, -1):
                if boxes[j] != boxes[r]:
                    continue
                if boxes[j] == boxes[r] and boxes[j+1] == boxes[r]:
                    continue
                dp[l][r][k] = max(dp[l][r][k], dfs(l, j, count) + dfs(j+1, idx, 0)) 
            return dp[l][r][k]
        return dfs(0, n-1, 0)
solution = Solution()
solution.removeBoxes(boxes = [1,3,2,2,2,3,4,3,1])
class Solution:
    def removeBoxes(self, boxes) -> int:
        # dp[l][r][k] 表示在 l-r 的区间长度内，在r后面还有 k 个元素 == boxes[r] 
        self.dp = [[[0] * 100 for _ in range(100)] for _ in range(100)]
        self.boxes = boxes
        self.n = len(boxes)
        return self.dfs(0, self.n - 1, 0)
    
    def dfs(self, l, r, k):
            if l > r: 
                return 0
            if self.dp[l][r][k] != 0:
                return self.dp[l][r][k]
            
            idx = r
            count = k
            while idx >= l and self.boxes[idx] == self.boxes[r]:
                idx -= 1
                count += 1
                
            # 第一种情况
            self.dp[l][r][k] = self.dfs(l, idx, 0) + count * count
            # 第二种情况
            j = idx
            while j >= l:
                if self.boxes[j] != self.boxes[r]:
                    continue
                if self.boxes[j] == self.boxes[r] and self.boxes[j+1] == self.boxes[r]:
                    continue
                self.dp[l][r][k] = max(self.dp[l][r][k], self.dfs(l, j, count) + self.dfs(j+1, r-1, 0)) 
                j -= 1
            return self.dp[l][r][k]<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1688026363969242, 'fraction_numerical': 0.039912120102526545, 'mean_word_length': 1.3310580204778157, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '183256', 'license': 'Apache-2.0', 'n_tokens_mistral': 1214, 'n_tokens_neox': 1160, 'n_words': 240, 'path': 'Dynamic Programming/1108/546. Remove Boxes.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '2731'}