給出一些不同顏色的盒子，盒子的顏色由數(shù)字表示，即不同的數(shù)字表示不同的顏色。
你將經(jīng)過若干輪操作去去掉盒子，直到所有的盒子都去掉為止。每一輪你可以移除具有相同顏色的連續(xù) k 個盒子（k?>= 1），這樣一輪之后你將得到 k*k 個積分。
當(dāng)你將所有盒子都去掉之后，求你能獲得的最大積分和。

示例：

輸入：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

動態(tài)規(guī)劃

首先，假設(shè)我們拿到的 boxes 長這樣：

假設(shè)我們經(jīng)過一系列操作后消掉了其中一些盒子：

對于這樣一個子序列，我們就可以記錄到dp數(shù)組里。我們可以操作的范圍是l到r的子序列。由于我們對每個子序列默認(rèn)都是點(diǎn)擊boxes[r]來消除，因此要知道r的后面還連著幾個與boxes[r]相同顏色的盒子，記為k。如下圖，l = 0, r = 6, k = 2， 將其能獲得的最高得分記在dp[0][6][2]。

現(xiàn)在我們調(diào)用 calculatePoints(i, r, k) 來計算它的最高得分 dp[i][r][k]。

calculatePoints(i, r, k)

在我們這個子序列中，dp[0][6][2] 與 dp[0][5][3] 實(shí)際上是等價的。我們將r向左一直移動到不能再移動為止。

接著，我們計算出不同策略的得分，取最高分。

策略 1

我們可以直接點(diǎn)boxes[r]，把最后4個盒子一次性消除，獲得16分！

剩下的盒子成為這樣一個子序列 dp[0][4][0]：

策略1得分：4*4 + dp[0][4][0]

策略 2

我們還可以把夾在中間的雜魚盒子都消掉，讓后面連起來的盒子數(shù)更多：

為了找到可以跟 boxes[r] 連起來的盒子，令 i = l：

i++

直到 boxes[i] == boxes[r]，就說明我們搜索到了

在這個例子中，消掉雜魚盒子能獲得的分?jǐn)?shù)是 dp[3][4][0]。

剩下的盒子的得分是 dp[0][2][4] 。

綜上，策略2得分：dp[0][2][4] + dp[3][4][0]

總結(jié)

為了取得一個子序列的最高得分，我們分不同策略，每種策略的得分可以看作是1~2個子子序列的最高分之和。

Code

def removeBoxes(self, boxes: List[int]) -> int:def dp(l, r, n):nonlocal memo, boxesif memo.get((l, r, n)):return memo[(l, r, n)]if l == r - 1:return (n + 1) * (n + 1)if boxes[l] == boxes[l + 1]:return dp(l + 1, r, n + 1)res = (n + 1) * (n + 1) + dp(l + 1, r, 0)for l2 in range(l + 2, r):if boxes[l2] == boxes[l]:res = max(res, dp(l + 1, l2, 0) + dp(l2, r, n + 1))memo[(l, r, n)] = resreturn resmemo = {}return dp(0, len(boxes), 0)

復(fù)雜度分析

• 時間復(fù)雜度：O(n4)O(n^4)O(n4)。最壞情況下每個 $f(l,r,k)$ 被計算一次，每次狀態(tài)轉(zhuǎn)移需要 $O(n)$ 的時間復(fù)雜度。
• 空間復(fù)雜度：O(n3)O(n^3)O(n3)。$\mathrm{d}\mathrm{p}$ 數(shù)組的空間代價是 O(n3)O(n^3)O(n3)，遞歸使用棧空間的代價為 $O(n)$。

總結(jié)

以上是生活随笔為你收集整理的546. Remove Boxes 移除盒子的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。