動機

三維dp!? 這真的能在45分做出來?

Problem

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.

 

Example 1:

Input: boxes = [1,3,2,2,2,3,4,3,1]Output: 23Explanation:[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)

Example 2:

Input: boxes = [1,1,1]Output: 9

Example 3:

Input: boxes = [1]Output: 1

 

Constraints:

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

Sol

dp去模擬移除箱子的過程，dp(i,j)是範圍中的最大分數，k是與j的顏色相同的箱子個數

之後就是兩個case

  • 把累績到現在的盒子花掉
  • 累積箱子

BACAA: dp(0,4,0) BA|AA: dp(0,1,2) B|AAA: dp(0,1,3)

想從dp(0,4,0)變成dp(0,1,3) BACA|A: dp(0,3,1)+dp(4,3,0) BAC|AA:dp(0,2,2)+dp(3,4,0) B|AAA: dp(0,1,3)+...

class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        @cache
        def dp(i,j,k):
            if i > j:
                return 0
            else:
                ret = dp(i,j-1,0)+(k+1)**2
                divs = [dp(i,x,k+1)+dp(x+1,j-1,0) for x in range(i,j) if boxes[x] == boxes[j]]
                return max(ret,max(divs,default=0))
        return dp(0,len(boxes)-1,0)