是第一个的衍生，DP的重复使用
第一个DP是记录i到j是否是回文；于此同时另一个DP是记录i到j需要最小的隔板数目。
这里需要注意的是第二个DP的思想r[i]=min{r[i],r[j+1]+1}这个深层次的思想是，或许当前默认的cut数目或者是第j+1个位置的cut数目加1.
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.
public class Solution {public int minCut(String s) {int[] r=new int[s.length()+1];for(int i=0; i<r.length; i++)r[i]=r.length-2-i;boolean[][] f=new boolean[s.length()][s.length()];for(int i=s.length()-1; i>=0; i--)for(int j=i; j<s.length(); j++){if(s.charAt(i)==s.charAt(j)&&(j-i<=1 || f[i+1][j-1]==true)){f[i][j]=true;r[i] = Math.min(r[i],r[j+1]+1);}}return r[0];}
}