动态规划-回文串问题——132.分割回文串II

1.题目解析

题目来源：132.分割回文串II——力扣

测试用例

2.算法原理

首先回文串问题一定首先需要保存每个回文子串出现的位置，即二维dp表来存储所有子字符串中符合回文子串的位置，如图

1.状态表示

创建一个一维dp表来存储第i个位置之前的字符串数组全部划分为回文子串需要切的最小分割次数

即dp[i]:以第i个位置为结尾的子字符串全部划分为子字符串所需要分割的最小次数

2.状态转移方程

当[0,i]位置的字符串是回文子串时就不用分割，因此dp[i]=0，反之需要创建新的指针j（1<=j <=i）在[1,i]之间寻找(因为单个字符一定是回文子串所以第一个字符无需判断，这里j就直接从1开始遍历)，当[j,i]区间的字符串是回文子串时就需要更新最小分割数，即dp[i]=min(dp[i],dp[j-1]+1)

3.初始化

因为需要求最小分割数，所以求min值时为了原来未填写的dp表中的数字不干扰，就可以将dp表初始化为INT_MAX

4.填表顺序

从左到右依次填写

5.返回值 

返回最后一个位置dp表的值

3.实战代码

代码分析 

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> isPal(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j]) {
                    isPal[i][j] = i + 1 < j ? isPal[i + 1][j - 1] : true;
                }
            }
        }
        vector<int> dp(n, INT_MAX);
        for (int i = 0; i < n; i++) {
            if (isPal[0][i]) {
                dp[i] = 0;
            } else {
                for (int j = 1; j <= i; j++) {
                    if (isPal[j][i]) {
                        dp[i] = min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[n - 1];
    }
};