給定一個字符串 s，將 s 分割成一些子串，使每個子串都是回文串。

返回符合要求的最少分割次數。

示例:

輸入:?"aab"
輸出: 1
解釋: 進行一次分割就可將?s 分割成 ["aa","b"] 這樣兩個回文子串。

思路：dp[i]代表前i個分割最小數，如果本身就是回文，那么dp[i]=0，否則它可以和任意比i小的起點組成字符串，某個字符串如果是回文，它的起點記為j，那么dp[i]就可能等于dp[j]?+?1，也就是到為止的最優解加上剛發現的回文串。而最優解就是這些答案中最小的，dp[i]?=?Math.min(dp[i],?dp[j]?+?1);。

當然，檢查是否是回文串是很耗時的，可以用馬拉車來預先算出，這里懶得找了。

public class Solution {public int minCut(String s) {int len = s.length();if (len < 2) return 0;int[] dp = new int[len];for (int i = 0; i < len; i++) dp[i] = i;for (int i = 1; i < len; i++) {if (checkPalindrome(s, 0, i)) {dp[i] = 0;}else{for (int j = 0; j < i; j++)if (checkPalindrome(s, j + 1, i))dp[i] = Math.min(dp[i], dp[j] + 1);}}return dp[len - 1];}private boolean checkPalindrome(String s, int left, int right) {while (left < right) {if (s.charAt(left) != s.charAt(right)) return false;left++;right--;}return true;}
}

?