Leetcode 546: Remove Boxes

Published in

learning note

Aug 14, 2021

Difficulty: Hard (10 personal rank)
Keywords: DP

前言

這題是我近期看過最難的DP問題，這題的難點在於，可能為了拚湊出連續的數字，故意先挖掉一部分，從而使數值變得連續，所以我直覺會想要有一個結構能夠表達破碎的陣列狀態，但實際上稍微想想就知道這樣複雜度超高，那如何設計使的狀態更為簡單，就是本例的難點。

在寫這題時，我回想到有另外兩題也有類似的難點，但這幾題都得用不同的想法去面對。

給出一些不同顏色的盒子，盒子的顏色由數字表示，即不同的數字表示不同的顏色。

你將經過若干輪操作去去掉盒子，直到所有的盒子都去掉為止。每一輪你可以移除具有相同顏色的連續 k 個盒子（k >= 1），這樣一輪之後你將得到 k * k 個積分。

當你將所有盒子都去掉之後，求你能獲得的最大積分和。範例如下：

對於一個區間為 [9, 5, 3, 5, 3, 3, 9, 8, 8, 5, 3, 9, 6]的狀態來說，對於最左邊的9，我們有兩個選擇，分別為

單獨拿走，並將積分加上1*1
不單獨拿走，也就是考慮這個9跟其他的9進行搭配的可能性，以本例來說這時有兩種選擇，第一種為先挖掉[5,3,5,3,3]，使的陣列變成[9, 9, 8, 8, 5, 3, 9, 6]；第二種為先挖掉 [5, 3, 5, 3, 3, 9, 8, 8, 5, 3]，使的陣列變成[9, 9, 6]。

關於第二種選擇的其中一個狀態為 [9, 9, 8, 8, 5, 3, 9, 6]，也代表已經保證最左邊兩個9都不可分開，我們可以再嘗試要2個9一起消除還是再挖掉中間一部分變成[9,9,9,6]，此時變成前3個數字都綁定在一起。

因此對於狀態來說，可以表達成(L, R, K)，代表在區間[L, R]中，因為我們曾經進行過若干次挖空，導致目前還有K筆跟L位置一樣顏色的盒子，是跟L連在一起尚未消除。

這個寫法的K意思為：R右邊累積至今，有幾個數字跟R一樣且還未消除。所以程式碼是從右邊往左邊看，不過本質跟上面的敘述相同。