【Leetcode】1246. Palindrome Removal

题目地址：

https://leetcode.com/problems/palindrome-removal/description/

给定一个长$n$数组$A$，每次允许删除一段回文子数组，问至少多少次可以将整个数组删完。

设$f[l][r]$是$A[l:r]$这一段至少删多少次可以删光，那么答案就是$f[0][n-1]$。如果$l=r$显然$f[l][r]=1$；如果$l+1=r$，显然当$A[l]=A[r]$的时候$f[l][r]=1$，否则$f[l][r]=2$；考虑一般情形，如果$A[l]=A[r]$，那么有一种方案，其是在$f[l+1][r-1]$的方案里最后一次删的时候，顺便将两个端点删掉，从而$f[l+1][r-1]$是可能的最小值，此外，如果不是这样的删法，可以枚举删掉左端点的时候，那一次删除的右端点的位置，则 f [ l ] [ r ] = min ⁡ l ≤ k < r { f [ l ] [ k ] + f [ k + 1 ] [ r ] } f[l][r]=\min_{l\le kf[l][r]=minl≤k<r​{f[l][k]+f[k+1][r]}。代码如下：

class Solution {
 public:
  int minimumMoves(vector<int>& A) {
    int n = A.size();
    int f[n][n];
    memset(f, 0x3f, sizeof f);
    for (int len = 1; len <= n; len++)
      for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        if (len == 1) f[l][r] = 1;
        else if (len == 2) f[l][r] = A[l] == A[r] ? 1 : 2;
        else {
          if (A[l] == A[r]) f[l][r] = f[l + 1][r - 1];
          for (int k = l; k < r; k++)
            f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);
        }
      }

    return f[0][n - 1];
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度$O(n^3)$，空间$O(n^2)$。