Leetcode#132 Palindrome Partitioning II

原题地址

动态规划题。

最直观的想法就是用cut[i][j]表示子串s[i..j]的最小分割数，则有如下规则：

1. 如果s[i..j]是回文串，则cut[i][j]=0

2. 如果s[i..j]不是回文串，则枚举分割点，将原字符串切成两个子串，求解子问题。递推公式：cut[i][j] = min{cut[i][k] + cut[k+1][j] + 1}，i <= k < j

这样做的时间复杂度是O(n^3)，可以引入额外的辅助条件对递推数组降维来优化。

改进后是这样的：

令cut[i]表示子串s[i..n-1]的最小分割数，则有如下规则：

1. 如果s[i..n-1]是回文串，则cut[i] = 0

2. 如果s[i..n-1]不是回文串，则枚举分割点，将原字符串切成两个子串，规定左边的那个串必须是回文串。递推公式：cut[i] = min{cut[k] + 1}，i < k < n 且 s[i][k-1]是回文串

时间复杂度降为O(n^2)

上面并没有考虑判断回文串的计算量，实际上这部分包含着大量重复计算， 所以必须要把是否是回文串的信息记录下来，以后要判断的时候直接查表即可。

算回文串也可以用动归解决。令palinp[i][j]表示s[i..j]是否是回文串，则palinp[i][j] = s[i] == s[j] && (j -i > 2 || palinp[i+1][j-1])，这部分的时间复杂度为O(n^2)

代码：

int minCut(string s) {
  if (s.empty())
    return 0;

  int len = s.length();
  bool **palinp = new bool*[len];
  int *cut = new int[len];

  for (int i = 0; i < len; i++)
    palinp[i] = new bool[len];

  for (int l = 1; l <= len; l++) {
    for (int i = 0; i + l <= len; i++) {
      palinp[i][i + l - 1] = (s[i] == s[i + l - 1]) && (l <= 2 || palinp[i + 1][i + l - 2]);
    }
  }

  for (int i = len - 1; i >= 0; i--) {
    if (palinp[i][len - 1])
      cut[i] = 0;
    else {
      cut[i] = len - i - 1;
      for (int j = i + 1; j < len; j++) {
        if (palinp[i][j - 1])
          cut[i] = min(cut[i], 1 + cut[j]);
      }
    }
  }

  return cut[0];
}