leetcode--20. palindrome-partit

题目：
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s ="aab",
Return 1 since the palindrome partitioning["aa","b"]could be produced using 1 cut.

给定字符串s，分区的每个子字符串都是回文。返回s的回文分区所需的最小切割数。
例如，给定s=“aab”，返回1，因为回文分区[“aa”，“b”]可以切割1次生成

思路：
动态规划
dp[i] - 表示子串（0，i）的最小回文切割，则最优解在dp[s.length-1]中

分几种情况：

1.初始化：当字串s.substring(0,i+1)(包括i位置的字符)是回文时，dp[i] =0(表示不需要分割)；否则，dp[i] = i（表示至多分割i次）

2.对于任意大于1的i，如果s.substring(j,i+1)(j<=i,即遍历i之前的每个子串)是回文时，dp[i] = min(dp[i]，dp[j-1]+1)；

3.如果s.substring(j，i+1)(j<=i)不是回文时，dp[i] = min(dp[i],dp[j-1]+i+1-j)；

public class Solution {
    public int minCut(String s) {
     int[] dp = new int[s.length()];
      for(int i=0;i<s.length();i++){
          dp[i] = isPalindrome(s.substring(0, i+1))?0:i;
          if(dp[i] == 0)
              continue;
          for(int j=1;j<=i;j++){
              if(isPalindrome(s.substring(j, i+1)))
                  dp[i] = Math.min(dp[i], dp[j-1]+1);
              else
                  dp[i] = Math.min(dp[i], dp[j-1]+i+1-j);
          }
      }
      return dp[dp.length-1];
    }
    
    private boolean isPalindrome(String s){
        return new StringBuffer(s).reverse().toString().equals(s);
    }
}