1278. 分割回文串 III

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

考点

  • 划分DP
  • 回文串

思路

划分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
29
30
31
32
class Solution {
 public:
  static const int inf = 0x3f3f3f3f;
  int palindromePartition(string s, int k) {
    int n = s.size();
    s = "0" + s;
    int cost[105][105];
    memset(cost, 0, sizeof(cost));
    // 双指针打表回文串开销
    for (int i = n; i >= 1; --i) {
      for (int j = i + 1; j <= n; ++j) {
        if (j - i < 2)
          cost[i][j] = (s[i] != s[j]);
        else
          cost[i][j] = cost[i + 1][j - 1] + (s[i] != s[j]);
      }
    }
    // DP
    int f[105][105];
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int j = 1; j <= k; ++j) {
      for (int r = j; r <= n; ++r) {
        for (int l = r; l >= j; --l) {
          if (f[j - 1][l - 1] != inf)
            f[j][r] = min(f[j][r], f[j - 1][l - 1] + cost[l][r]);
        }
      }
    }
    return f[k][n];
  }
};