回文串划分 leetCode 132 Palindrome Partitioning II

回文串划分

输入小写字符串，划分成尽量少的回文串。输出最小切分数
输入：aaadbccb
输出：2
aaa、d、bccb需要两刀分割成3个回文子串。

分析

d[i]表示input.substring(0,i)子串的最少回文子串个数
状态转移：d[i]=min(d[j]+1|input.substring(j,i)是回文）
刀数 = 回文子串数-1

代码块

public class Solution {
    public int minCut(String s) {
    int n = s.length();boolean[][] isPalindrome = new boolean[n][n];//预处理回文判断for(int i=0;i<n;i++){
    //i center 枚举中心//oddisPalindrome[i][i] = true;for(int j=1;i-j>=0&&i+j<n;j++){
    //向左右延伸标记子串是回文串，直到左右字符不同为止if(s.charAt(i-j)==s.charAt(i+j)){
    isPalindrome[i-j][i+j] = true;}else break;                    }//evenfor(int j=1;i+j<n&&i-j+1>=0;j++){
    if(s.charAt(i-j+1)==s.charAt(i+j))isPalindrome[i-j+1][i+j] = true;else break;}}int[] d = new int[n+1];//动态规划求前i个子串的最小回文串的个数d[0] = 0;//0 chars 0个字符的边界情况只有0个回文子串for(int i=1;i<=n;i++){
    d[i] = Integer.MAX_VALUE;}for(int i=1;i<=n;i++){
    for(int j=0;j<=i-1;j++){
    if(isPalindrome[j][i-1]){
    d[i] = Math.min(d[i],d[j]+1);//状态转移}}}return d[n]-1;}}