博文中会简要介绍Leetcode P0132题目分析及解题思路。
“Palindrome Partitioning II”这道题是p0131的变形题，这道题可以用两次动态规划解决。一次是确定回文子串，另一次是一个一维费用背包问题。
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.
首先是确定所有回文子串。我们可以借鉴p0005的思路，得到如下递推表达式，
dp[i][j] = dp[i+1][j-1]+2, if dp[i+1][j-1] > 0 && s[i] == s[j]
其中dp[i+1][j-1] > 0表示字符串i+1到j-1的子串是一个回文串，s[i] == s[j]则意味着两端字符相等。
然后根据获得到的所有回文子串的区间，我们可以利用一维费用背包的思路，获得最小合法分割的次数。递推表达式如下，
dp2[0][i] = 0, if dp1[0][i] == true,
如果字符串s[0:i]是一个回文串，则切割次数为0，
dp2[0][i] = min(dp2[0][i], dp2[0][j-1]+1), if dp1[j][i] == true,
如果字符串s[j:i]是一个回文串，则切割次数为前j个字符，即s[0:j-1]的切割次数加上1，最终取得所有的最小值。
以下是Java的题解代码实现。
class Solution {
public int minCut(String s) {
int N = s.length();
boolean[][] dp1 = new boolean[N][N];
char[] chars = s.toCharArray();
for (int idx=0; idx<N; ++idx) {
dp1[idx][idx] = true;
if (idx > 0 && chars[idx] == chars[idx-1])
dp1[idx-1][idx] = true;
}
// DP1
for (int i1=2; i1<N; ++i1) {
for (int j2=i1-2; j2>=0; --j2) {
dp1[j2][i1] = dp1[j2+1][i1-1] && (chars[i1] == chars[j2]);
}
}
// DP2
int[][] dp2 = new int[N][N];
for (int i1=0; i1<N; ++i1) {
dp2[0][i1] = Integer.MAX_VALUE;
for (int j2=i1; j2>=0; --j2) {
if (!dp1[j2][i1])
continue;
dp2[0][i1] = Math.min(dp2[0][i1], (j2 == 0)? 0: dp2[0][j2-1]+1);
}
}
return dp2[0][N-1];
}
}