0132.分割回文串 II

https://leetcode.cn/problems/palindrome-partitioning-ii/

方法一：动态规划

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

class Solution {
 public:
  int minCut(string s) {
    int n = s.size();
    vector<vector<bool>> g(n, vector<bool>(n, false));
    // construct palindrome map
    for (int end = 0; end < n; end++) {
      for (int start = 0; start <= end; start++) {
        if (s[start] == s[end] && (end - start < 2 || g[start + 1][end - 1])) {
          g[start][end] = true;
        }
      }
    }
    // define dp[n], dp[x] means min Cut
    vector<int> dp(n);
    iota(dp.begin(), dp.end(), 0);
    for (int end = 1; end < n; end++) {
      for (int start = 0; start <= end; start++) {
        if (g[start][end]) {
          dp[end] = min(dp[end], start ? dp[start - 1] + 1 : 0);
        }
      }
    }
    return dp[n - 1];
  }
};