132. Palindrome Partitioning II

相关问题：131. Palindrome Partitioning（Backtracking解法）

问题：（DP解法）

给定字符串，求最少切分几次，使得每一个切片都是回文字符串。

Example 1:
Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:
Input: s = "a"
Output: 0

Example 3:
Input: s = "ab"
Output: 1

Constraints:
1 <= s.length <= 2000
s consists of lower-case English letters only.

　　

解法：DP（动态规划）

⚠️  注意：本问题不能用通用字符串dp[i][j]来表示字符串子串s[i~j]的所求结果。（状态转移较为难）

本问题设状态：

• dp[i]：字符串s[0~i]需要最少切的次数。

base状态：

• dp[i]：每个字符都是独立个体，最多切 i 刀（每对相邻字符之间都切）。

状态转移：

对于每一个位置 i：作为回文串中心

• 奇数回文串：
  • 【i-j】...【i-1】【i】【i+1】...【i+j】，向两边扩展 j，若一直是回文串，那么可以缩减字符串 [i-j ~ i+j] 为一个切片。dp[i+j] = dp[i-j -1] + 1（回文串的前一个位置之前的最小cut数+1）
• 偶数回文串：
  • 【i-j+1】...【i】｜【i+1】...【i+j】，向两边扩展 j，若一直是回文串，那么可以缩减字符串 [i-j+1 ~ i+j] 为一个切片。dp[i+j] = dp[i-j+1 -1] + 1

当然，多次循环中，dp[i+j]自己也许有更小的值，因此，每次对自己求最小值。

代码参考：

class Solution {
    //dp[i]:the minimum cuts the s[0~i] needs
public:
    int minCut(string s) {
        int n = s.size();
        vector<int> dp(n+1, 0);
        //initial
        for(int i=0; i<=n; i++) dp[i] = i-1;//every char is seemed not Pal.
        //dp
        for(int i=0; i<n; i++){//for each char as mid, expand to both side to check if a Pal.
            for(int j=0; i-j>=0 && i+j<n; j++) {//odd: i-1 i i+1
                if(s[i+j]==s[i-j]) {//if Pal
                    dp[i+j+1] = min(dp[i+j+1], dp[i-j]+1);
                } else {
                    break;
                }
            }
            for(int j=1; i-j+1>=0 && i+j<n; j++) {//even: i | i+1
                if(s[i+j]==s[i-j+1]) {//if Pal
                    dp[i+j+1] = min(dp[i+j+1], dp[i-j+1]+1);
                } else {
                    break;
                }
            }
        }
        
        return dp[n];
    }
};