題目網址：https://leetcode.cn/problems/remove-boxes/

題意：給一些不同顏色的盒子 boxes, 盒子的顏色由不同的正數表示。

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

返回你能獲得的最大積分和。

Solution：

想法：我們很容易陷入這樣一個錯誤的思路：用 dfs(l, r) 來表示移除區間 [l, r] 內所有的盒子能得到的最大積分, 然後去探索某一種移除盒子的策略來進行狀態轉移。但實際上, 我們並不能直接使用起點和終點來決定最大分數, 因為這個分數並不只依賴於 subarray, 也依賴於之前的移動對 array 的影響（概念類似 312. Burst Balloons）, 最終的 subarray 在原先的 array 中可能不是連續的。

e.g. boxes = [3,4,2,4,4]

  • 若先移除 2, 使 [3,4,2,4,4] ➔ [3,4,4,4], 再移除 3 個 4
    ➔ 對積分的貢獻為 $1^2 + 3^2 = 10$
  • 若先移除右邊 2 個 4, 使 [3,4,2,4,4] ➔ [3,4,2], 再移除 4 和 2
    ➔ 對積分的貢獻為 $2^2 + 1^2 + 1^2 = 6$
  • 顯然先移除 2 的方案比較好, 但剩下的 3 個 4 在原先的 array 中並不是連續的

➔ 利用 DFS + Memorization, 因為本題 bottom-up 的 DP 不好做

1. 定義狀態：

  • dfs(l, r, k)：移除區間 boxes[l:r] 的盒子, 加上該區間右邊等於 boxes[r] 的 k 個元素所能獲得的最大積分

    e.g. boxes = [l, l+1, ..., r-1, r, 值同r, 值同r, 值同r]

    • index = r 的右邊有 3 個元素和 boxes[r] 相同, 故 k = 3。因為有 3 個和 r 相同, 故可以消掉 4 個, 所以加上 4 * 4
      ➔ dp[l][r][3] = dp[0][r - 1][0] + 4 * 4

    • 因此, 得到初始條件 dp[l][r][k] = dp[l][r - 1][0] + pow(k + 1, 2)

    • 但是, 也有可能在 boxes[l:r] 中存在和 boxes[r] 值相同的元素

      • e.g. boxes = [l, l+1, ..., i, i+1, ..., r-1, 值同i(原來是r), 值同i(原來是r+1), 值同i(原來是r+2), 值同i(原來是r+3)]（假設 boxes[i] == boxes[r]）
      • 先移除 boxes[i+1:r-1], 使原來的 dp[l][r][3] 中的 k = 3 變的更大, 但是 r 變得更小, 這樣有機會使積分和更大
        • 先移除 boxes[i+1:r-1] 的最大積分和為 dp[i + 1][r - 1][0]
        • 移除剩餘部分 [l, l+1, ..., i, 值同i(原來是r), 值同i(原來是r+1), 值同i(原來是r+2), 值同i(原來是r+3)] 的最大積分和為 dp[l][i][k + 1]

      ➔ dp[l][r][k] = dp[i + 1][r - 1][0] + dp[l][i][k + 1]

2. 得到轉移方程：

  • 先將 dp[l][r][k] 初始為 dp[l][r - 1][0] + pow(k + 1, 2)
  • 當 boxes[i] == boxes[r] 時, dp[l][r][k] = max(dp[l][r][k], dp[i + 1][r - 1][0] + dp[l][i][k + 1])。其中, l ≤ i < r

3. 初始化：

  • 初始積分皆設為 0
class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        const int n = boxes.size();
        dp.resize(n, vector<vector<int>>(n, vector<int>(n, 0)));
        return dfs(boxes, 0, n - 1, 0);
    }

private:
    vector<vector<vector<int>>> dp;

    int dfs(const vector<int>& boxes, const int l, const int r, const int k){
        if (l > r) {
            return 0;
        }

        if (dp[l][r][k] != 0) {
            return dp[l][r][k];
        }

        dp[l][r][k] = dfs(boxes, l, r - 1, 0) + pow(k + 1, 2);

        for (int i = l; i < r; ++i) {
            if (boxes[i] == boxes[r]) {
                dp[l][r][k] = max(dp[l][r][k], dfs(boxes, i + 1, r - 1, 0) + dfs(boxes, l, i, k + 1));
            }
        }

        return dp[l][r][k];
    }
};
  • time：$O(n^4)$ ➔ 計算每個 dfs(l, r, k) 需 $O(n)$, 因為 for loop 不超過 $O(n)$。總共有 $O(n^3)$ 個狀態, 且計算每個狀態需 $O(n)$
  • space：$O(n^3)$ ➔ dp