132. 分割回文串 II
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
回文串
。
返回符合要求的 最少分割次数
思路：
规定dp[i]是以i位置为最后一个元素，（0-i）的最少分割次数，此时需要从（0-i-1）中找出一个j，使得（j，i）是一个回文串，这样的话可以看成实在j位置切了一刀，然后（0-j-1）的最少切割存放在dp[j-1]中，则dp[i]=dp[j-1]+1（加一是在j位置又切了一刀）。
细节：由于j是默认从0位置开始计算的，则当j=0时，即（0，i）本身可以构成一个回文串，而j-1是下标-1，dp中没有下标为-1的元素，因此需要单独说明此时dp[i]=0(因为整体是一个回文串，因此可以一刀不切)，如果想和j等于别的值保持一致，则dp需要开辟N+1个空间，第一个空间dp[0]=-1,dp[i]表示已i-1位置元素为最后一个元素切割的最小次数。
class Solution {
public:bool judge(vector<int>&dp1, vector<int>&dp2, int left, int right){if ((right -left+1) % 2 == 0)return dp2[(right +left) / 2] >= right - left+1;elsereturn dp1[(right + left) / 2] >= right - left+1;}int minCut(string s) {int n = s.size();vector<int>dpone(n, 1);vector<int>dptwo(n, 0);for (int i = 0; i < n; i++){int j = 1;while (i - j >= 0 && i + j < n && s[i - j] == s[i + j]){dpone[i] += 2;j++;}j = 0;while (i - j >= 0 && i + 1 + j < n && s[i - j] == s[i + j + 1]){dptwo[i] += 2;j++;}}vector<int>dp(n, INT_MAX);dp[0] = 0;for (int i = 1; i < n; i++){for (int j = 0; j <= i; j++){if (judge(dpone, dptwo, j, i)){if (j == 0)dp[i] = 0;elsedp[i] = min(dp[j-1] + 1, dp[i]);}}}return dp.back();}
};
