132. 分割回文串 II

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

考点

  • 回文串
  • 划分DP

题解

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
class Solution {
 public:
  static const int inf = 0x3f3f3f3f;
  int minCut(string s) {
    // 打表，下标l~r之间是否为回文串
    bool isP[2005][2005];
    memset(isP, 0, sizeof(isP));
    int n = s.size();
    for (int i = n - 1; i >= 0; --i) {
      for (int j = i; j < n; ++j) {
        if (s[i] == s[j] && (j - i < 2 || isP[i + 1][j - 1])) isP[i][j] = 1;
      }
    }
    int f[2005];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int r = 0; r < n; ++r) {
      if (isP[0][r]) {
        f[r] = 0;
        continue;
      }
      for (int l = r; l >= 1; --l) {
        if (isP[l][r]) f[r] = min(f[r], f[l - 1] + 1);
      }
    }
    return f[n - 1];
  }
};

思路

裸的划分DP+回文串判定模板，直接看代码即可