Solution 1

实际上就是承接了 0131. Palindrome Partitioning 的设计思路，使用动态规划 进行处理。

【参考官方】整个过程有两个优化要求：

1. 划分的枚举最优化：动态规划（）
2. 回文判定的最优化：动态规划（0005. Longest Palindromic Substring 或 0131. Palindrome Partitioning ）

第二个已经实现过了，主要是第一个不好处理，这里学习了官方的方法： a n s [ i ] ans[i] ans[i]表示到i为止子串的最优划分方案，其中 a n s [ i ] ans[i] ans[i]在整个子串都为回文时初始化为0，否则为MAX。

状态转移方程为： a n s [ j ] = min ⁡ ( a n s [ j ] , a n s [ i − 1 ] + 1 ) ans[j] = \min(ans[j], ans[i - 1] + 1) ans[j]=min(ans[j],ans[i−1]+1) ，其中i和j分别为当前有效回文判定的首尾索引。

整个处理的思路就是两个DP：第一个DP对所有的划分方案的回文情况判定，第二个基于这个判定计算最优的划分方案。

• 时间复杂度： O ( n 2 ) O(n^2) O(n2)，其中 n n n为输入的字符串长度，dp的二维遍历
• 空间复杂度： O ( n 2 ) O(n^2) O(n2)，其中 n n n为输入的字符串长度，dp的二维遍历需要二维数组占用

class Solution {
public:
    int minCut(string s) {
        int len = s.size();
        
        vector<vector<bool>> dp(len, vector<bool>(len, false)); 
        vector<int> ans(len, INT_MAX);
        
        for (int j = 0; j < len; ++j) { // 参考0005 先迭代尾边界，对应第二个dp的顺序
             for (int i = 0; i <= j; ++i) {
                 if ((s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1])) {
										 // 参考0131 回文判定和dp数组的更新
                     dp[i][j] = true;
                     if (i == 0) {
                         ans[j] = 0;
                     } else {
                         ans[j] = min(ans[j], ans[i - 1] + 1);
                     }
                 }
            }
        }
        
        return ans[len - 1];
    }
};

Solution 2

Solution 1的Python实现

class Solution:
    def minCut(self, s: str) -> int:
        length = len(s)
        
        dp = [[False] * length for i in range(length)]
        ans = [None] * length
        
        for j in range(length):
            for  i in range(j + 1):
                if (s[i] == s[j]) and (j - i <= 2 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    if i == 0:
                        ans[j] = 0
                    else:
                        ans[j] = ans[i - 1] + 1 if ans[j] is None else min(ans[j], ans[i - 1] + 1)
                        
        return ans[length - 1]