题解 | #分割回文串-ii#

import java.util.*;
/**
 * 思路: 动态规划
 *   问题: 求将s分割为每一段都是回文串的的最小分割数
 *   子问题: 将s的一部分分割为回文串的次数
 *   状态:  将s的前i个字符分割为回文串的最小次数
 *   分析: 举例 aab, 初始状态1个字符的时候不需要分割, F[1] = 0, F[2] = 0(已经是回文串), F[3]=min(F[j])+1
 *   状态转移方程:
 *     1. 已经是回文串 F[i]=0
 *     2. if(j<i && s[j+1,i]是回文串) F[i] = min(F[j])+1
 */
public class Solution {

    public boolean isPal(String s, int start, int end){
        while(start<end){
            if(s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    public int minCut (String s) {
        if(s.length() == 0) return 0;
        int []minc = new int[s.length()+1];
        int len = s.length();
        for(int i=1; i<=len;i++){
            minc[i] = i-1;
        }
        for(int i=2; i<=len; i++){
            if(isPal(s, 0, i-1)) {
                minc[i] = 0;
                continue;
            }
            for(int j=0; j<i; j++){
                if(isPal(s, j, i-1)){
                    minc[i] = Math.min(minc[j]+1, minc[i]);
                }
            }
        }
        return minc[len];
    }
}