題目網址：https://leetcode.cn/problems/palindrome-removal/

題意：給一整數 array arr, 每次操作你都可以刪除一個回文 subarray arr[i], arr[i+1], ..., arr[j]（i ≤ j）。

每當你刪掉一個 subarray, 其右側元素會向前填補空位。

計算從 arr 中刪除所有數字所需的最少操作數。

Solution：

想法：利用 DP, 當找不出突破口時, 試著從最後一個元素下手

1. 定義狀態：

  • 首先, 會在 arr 前先加上一個 0, 代表什麼元素都沒有的狀態
  • dp[i][j]：arr[i:j] 刪除所有數字的最小操作數

2. 得到轉移方程：

  • 要在 arr[i:j] 中找回文, 就先判斷 arr[j] 要和哪個數消除

    • 若 arr[j] 和 arr[k] 相等時, 則一同消除, 其中 i ≤ k ≤ j
      ➔ dp[i][j] = dp[i + 1][k] + dp[k + 1][j - 1]
    • 當 dp[k + 1][j - 1] 不為空區間時, 則 arr[k]、arr[j] 可以被算在子區間的最後一次刪除中
      • e.g. arr = [1, 2, 3, 1] ➔ [0, 1, 2, 3, 1]
        • 其中 dp[2][3] = 2, 要刪除 [2, 3] 需操作 2 次
        • 由於 arr[1] == arr[4], 可以先刪除子區間中的 2, 此時 arr 變成 [1,3,1] 為回文, 故只要再刪一次

  • 狀態轉移方程：

    • dp[i][j] = min(dp[i][j], dp[i][k - 1] + max(1, dp[k + 1][j - 1]))
    • max(1, dp[k + 1][j - 1]) 是因為 k + 1 可能會越界。若越界, 根據 dp[i][j] 的定義, dp[k + 1][j - 1] 為空區間, 故設為 0。但此時要消除 dp[k][j] 的代價應為 1, 而不是 0
      • 當 dp[k + 1][j - 1] == 0 時, 取 1
      • 當 dp[k + 1][j - 1] != 0 時, 取 dp[k + 1][j - 1]

3. 初始化：

  • dp[0][0]：為空區間, 刪除所有數字的最小操作數 0
  • dp[i][i]：當區間中只有一個數時, 刪除所有數字的最小操作數 1。其中, 1 ≤ i ≤ n

4. 注意事項：

  • dp 的長度之所以要開 n + 2 而非 n + 1, 是因為 i ≤ k ≤ j
    ➔ dp[k + 1][j - 1] 中的 k + 1 最多是 n + 1, 故長度開 n + 2
class Solution {
public:
    int minimumMoves(vector<int>& arr) {
        const int n = arr.size();
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));

        arr.emplace(arr.begin(), 0);

        for (int i = 1; i <= n; ++i) {
            dp[i][i] = 1;
        }

        for (int len = 2; len <= n; ++len) {
            for (int i = 1; i + len - 1 <= n; ++i) {
                const int j = i + len - 1;
                dp[i][j] = INT_MAX; // 題目要取最小, 故初始值設最大

                for (int k = i; k <= j; ++k) {
                    if (arr[k] == arr[j]) {
                        dp[i][j] = min(dp[i][j], dp[i][k - 1] + max(1, dp[k + 1][j - 1]));
                    }
                }
            }
        }

        return dp[1][n];
    }
};
  • time：$O(n^3)$ ➔ for loop
  • space：$O(n^2)$ ➔ dp