递归回溯：Leetcode - 删除框 (Python)

Question

我正在研究这个 leetcode：https://leetcode.com/problems/remove-boxes/ 并且我的答案对于某些测试用例只是略有偏差。如有任何建议，我们将不胜感激。

问题简述如下：

You are given several boxes with different colors represented by different positive numbers.

You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (i.e., composed of k boxes, k >= >1), remove them and get k * k points.

Return the maximum points you can get.

示例 1：

Input: boxes = [1]
Output: 1 => (1*1)

示例 2：

Input: boxes = [1,1,1]
Output: 9 => (3*3)

示例 3：

Input: boxes = [1,3,2,2,2,3,4,3,1]
Output: 23
Explanation:
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 points) 
----> [1, 3, 3, 3, 1] (1*1=1 points) 
----> [1, 1] (3*3=9 points) 
----> [] (2*2=4 points)

我决定使用递归回溯来尝试解决这个问题，我的代码如下：

from copy import deepcopy as copy
class Solution: 
    # Main function
    def backtrack(self, boxes, score, seen={}):
        # Make list hashable
        hashable = tuple(boxes)
        
        if len(boxes) == 0:
            return score
        
        if hashable in seen:
            return seen[hashable]
        
        pos_scores = []
        
        loop_start = 0
        loop_end = len(boxes)
        
        while(loop_start < loop_end):
            # keep original boxes for original 
            box_copy = copy(boxes)
            
            # Returns the continous from starting point
            seq_start, seq_end = self.find_seq(box_copy, loop_start)
            
            # Return the box array without the seqence, and the score from removal
            new_boxes, new_score = self.remove_sequence(box_copy, seq_start, seq_end)
            
            # Backtrack based off the new box list and new score
            pos_scores.append(self.backtrack(box_copy, score+new_score, seen))
            
            # Next iteration will use a fresh copy of the boxes
            loop_start = seq_end
            
        seen[hashable] = max(pos_scores)
        return seen[hashable]
        
    def remove_sequence(self, boxes, start, end):
        rem_counter = 0

        for i in range(start, end):
            boxes.pop(i - rem_counter)
            rem_counter += 1

        dist = (end - start)
        score = dist * dist
        return boxes, score
    
    def find_seq(self, boxes, start):
        color = boxes[start]
        end = start

        for i in range(start, len(boxes)):
            if boxes[i] == color:
                end += 1
            else:
                break

        return start, end
    
    def removeBoxes(self, boxes) -> int:
        return self.backtrack(boxes, 0, {})

我的问题是我的代码适用于较小的示例，但不适用于较大的示例。我相信我的代码 almost 在那里，但我想我错过了一个边缘案例。任何提示将非常感谢。例如，我得到 [1,1,2,1,2] 以及大多数测试用例的正确答案。但是我对第三个例子的回答是 21，而不是 23。

Answer 1

根据@Armali 的评论，上述代码的解决方案是使用

        hashable = tuple(boxes), score

递归回溯：Leetcode - 删除框 (Python)

Recurive Backtracking: Leet Code - Remove Boxes (Python)

python

dynamic-programming

backtracking

recursive-backtracking