题目：

  1. 给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。
  2. 你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。
  3. 每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。
  4. 当你将所有盒子都去掉之后，求你能获得的最大积分和。
  6. 示例：
  8. 输入：boxes = [1,3,2,2,2,3,4,3,1]
  9. 输出：23
  10. 解释：
  11. [1, 3, 2, 2, 2, 3, 4, 3, 1] 
  12. ----> [1, 3, 3, 4, 3, 1] (3*3=9 分) 
  13. ----> [1, 3, 3, 3, 1] (1*1=1 分) 
  14. ----> [1, 1] (3*3=9 分) 
  15. ----> [] (2*2=4 分)
  17. 来源：力扣（LeetCode）
  18. 链接：https://leetcode-cn.com/problems/remove-boxes
  19. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

答案：

时间：

区间dp怎么越做越难，当然做不出了。

  1. class Solution:
  2.     def removeBoxes(self, boxes: List[int]) -> int:
  3.         n = len(boxes)
  4.         @functools.lru_cache(None)
  5.         def dfs(i,j,k):
  6.             if i>j:return 0
  7.             while i<j and boxes[j]==boxes[j-1]:
  8.                 j-=1
  9.                 k+=1
  10.             ans= (k+1)*(k+1) +dfs(i,j-1,0)
  11.             for p in range(i,j):
  12.                 if boxes[p]==boxes[j]:
  13.                     ans =max(ans,dfs(i,p,k+1)+dfs(p+1,j-1,0))
  14.             return ans
  15.         return dfs(0,n-1,0)

要点：

1. dp 定义：

从 L 到 R 且右边有 K 个和 R 一样的盒子。

2. 转移：

1. 先把 R 拉到可以拉到的最左边。然后把k+1个合并了（k个外面的和一个最后的）

2. 从左边遍历到右，一旦有与 R 一样的，进行中间消除的工作dfs(p+1,j-1,0)，然后把右边接过来，k就变成了k+1(多了个刚才找到的。)

其他：

我觉得我能读懂就很不错了。。。这种题没做过不可能会啊。

代码报错：无