Palindrome Partitioning II

这个题意思挺好理解，提供一个字符串s，将s分割成多个子串，这些字串都是回文，要求输出分割的最小次数。

Example:

Input: "aab"

Output: 1

Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

状态：这个题的状态也非常好理解，dp[i]表示将s[0..i]分割成回文子串的最小分割次数。然后不急于寻找状态转移方程，我们先要明确如何用代码判断一个字符串的某个部分是不是回文，其实也很好理解啊，咱们可以分块来理解，毕竟这是个算法题，不可能用常规的那种遍历一半的方式来判断。首先对于这个字符串的某个子串s[j..i](j<=i)，满足它是回文的条件两条（1）s[j]==s[i]  (2)  只确定两端的两个字符还不够，当这个子串的长度小于4或者去掉两端的相同字符后还是回文即可。现在我们除了递推数组dp，再定义一个记录数组pa[j][i]，如果s[j..i]是回文，则pa[j][i] = 1，否则为0。有了这两个条件，我们就可以总结状态转移方程了：

dp[i] = min(dp[j-1]+1)，当0<j<=i时，并且s[j..i]是回文时

dp[i] = 0 ,当j=0，并且s[j..i]是回文时

在具体的dp数组递推运算过程中，需要这两个分支，同时会更新pa[j][i]的值便于后面的过程中回文条件的判断。

 

1 public int minCut(String s) { 2         int slen = s.length(); 3         int[][]pa = new int[slen][slen]; 4         int[]dp = new int[slen]; 5         for(int i = 0;i