题目链接：https://leetcode-cn.com/problems/palindrome-partitioning-ii/description/
参考链接：https://blog.csdn.net/jingsuwen1/article/details/51934277
dp[i]存放[0,i)即以前i个字符串的子串的最小切割数，则所求为dp[s.length()];
前0个字符串和1个字符串不需要切割，所以dp[0]=0，dp[1]=0；
1.初始化：当字串s.substring(0,i)（[0,i)个字符）是回文时，dp[i] = 0(表示不需要分割)；否则，dp[i] = i-1（表示至多分割i-1次）;
比如abc最多切割2次（a|b|c），aa不需要切割
2.对于任意大于1的i，如果s.substring(j,i)( 1 =< j <= i ,即遍历i之前的每个子串)是回文时，dp[i] = min(dp[i], dp[j]+1);
(注：j不用取0是因为若j == 0，则又表示判断（0，i）)。
public int minCut(String s) {
if(s == null||s.length() == 0)
return 0;
int[] dp=new int[s.length()+1];
dp[0]=0;//空字符，不需要切割
dp[1]=0;
for (int i = 2; i < dp.length; i++) {
dp[i]=is_palindrome(s.substring(0,i))?0:i-1;
}
for(int i=2;i<=s.length();i++)
{
// 1=<j<=i的子串回文判定
for(int j=i;j>=1;j--)
{
if(is_palindrome(s.substring(j,i)))
{
dp[i]=Math.min(dp[i],dp[j]+1);
}
}
}
return dp[s.length()];
}
//判断回文串例程
public boolean is_palindrome(String s)
{
//System.out.println(s);
StringBuilder sb=new StringBuilder(s);
return s.equals(sb.reverse().toString());
}
上述的dp方法在leetcdoe上显示超时，在牛客网上可以通过。所以期待更加完全的dp方法。