2430. 对字母串可执行的最大删除数

发表于 分类于 阅读次数： Waline： 本文字数： 276 阅读时长 ≈ 1 分钟

考点

  • 划分DP
  • LCP

思路

从Push方向考虑，很容易写出下面的暴力DP：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int deleteString(string s) {
    int f[4005];
    int n = s.size();
    s = " " + s;
    memset(f, 0xcf, sizeof(f));
    f[0] = 0;
    for (int i = 0; i < n; ++i) {
      for (int len = 1; i + 2 * len <= n; ++len) {
        if (s.substr(i + 1, len) == s.substr(i + 1 + len, len))
          f[i + len] = max(f[i + len], f[i] + 1);
      }
      f[n] = max(f[n], f[i] + 1);
    }
    return f[n];
  }
};

但发现顺序遍历很难去掉substr，考虑逆序遍历，即f[i] = max(f[i], f[i + len] + 1)

那么就要判断s[i ~ n]与s[i + len ~ n]的最大公共前缀，即LCP的长度是否>= len

由此能得到下面的AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int deleteString(string s) {
    int n = s.size();
    s = " " + s;
    // LCP打表
    int lcp[4005][4005];
    memset(lcp, 0, sizeof(lcp));
    for (int i = n; i >= 1; --i) {
      for (int j = n; j > i; --j) {
        if (s[i] == s[j])
          lcp[i][j] = lcp[i + 1][j + 1] + 1;
        else
          lcp[i][j] = 0;
      }
    }
    // DP
    int f[4005];
    memset(f, 0xcf, sizeof(f));
    f[n + 1] = 0;
    for (int i = n; i >= 1; --i) {
      f[i] = 1;
      for (int len = 1; i + 2 * len - 1 <= n; ++len) {
        int j = i + len;
        if (lcp[i][j] >= len) f[i] = max(f[i], f[j] + 1);
      }
    }
    return f[1];
  }
};