132. Palindrome Partitioning II
这道题考的是怎么用dp来解决dfs的问题
如果仅使用dfs，即使加了剪枝，这道题还是超时，这时候要思考能不能用其他办法，比如dp，观察一下每一步之间有没有关联，通过记录历史，来节省时间。
- 怎么把前面的用到后面呢？
- 在哪些地方有潜在的dp？
思考
- 最优的情况是自己就是回文，最差的情况是拆成单个字符
- 怎么利用以前的信息？从而得到最小分割？
思路
-
怎么通过前面的最小分割，来更新新加入的字符对应的最小分割？
如果当前这个总的字符串是回文，自然结论为0分割；
若不是：
由于题目要求的是Minimum Cuts, 所以如果当前这个总的字符串不是回文，那我们要找到一个最小分割。
也就是说，出现了新的字符之后，如果不能达到令整个字符串都变成回文的效果，但是这个新加入的字符和原字符串后面的一部分组成新的回文（s[j+1,i]），那此时对应的分割数就是cutNum[j]+1。
这个查找过程可能会有多个匹配到的回文子串，我们选择最长的，使得cutNum[j]+1最小。
那么，如果往前找，没有找到回文字符串怎么办？最差的情况是把当前新加入的字符单独作为一个回文，这样切割数为cutNum[i-1]+1 -
要怎么在字符串里面，快速判断子字符串是否回文？
区间型动态规划
对于判断某一段是否是回文串，使用区间型动态规划可以将时间复杂度从O(n)优化到O(1)
使用一个二维boolean数组，来记录字符串 [i,j]是否回文。
以后每次判断都可以借助于以前记录的信息。
实现
-
使用一个数组 cutNum, 记录字符串s长度为０～i 的最小分割数目
-
初始化cutNum, 如果字符串[0,i] 是回文，那么cutNum[i] = 0, 否则minCus[i] = i (代表最多分割 i 次)
优化： 其实不需要*在这里进行初始化，因为后面DP的过程会一步一步计算出cutNum[i] -
当 i > 1，进入dp， 每一次更新minCust[i] 的时候, 从ｊ开始，ｊ--往前面移动，不断判断字符串s[j,i]是不是回文。如果是的话，说明字符串[0,j-1]和字符串[j,i]可以分成两部分，而且[j,i]是回文。我们只需要 cutNum[j-1] + 1就代表当前这种分割的最小分割。
在ｊ继续往前移动直到 j ==0的过程中，还可能遇到另外的回文组合形式，这时候也是计算cutNum[j-1]+1
把最小的cutNum[j-1]+1和cutNum[i]比较，取最小值更新cutNum[i] -
那么，怎么样快速查询子字符串是否回文呢？
使用空间动态dp
大致的思路：
matrix[i][j] == true 表示子字符串 s[i,j]是回文
什么情况下可以判断得到matrix[i][j]==true呢？如何利用以前的信息？
(1) matrix[j+1][i-1] == true && s[i] == s[j]
matrix[j+1][i-1]==true 表示sub(j+1,i-1)是满足回文字符串
或者
(2) i-j < 2 && s[i] == s[j]
如果 j - i == 1时，为相邻两个字符相等，
如果 j - i == 0时，为同一个字符）
总结
根据遍历字符串的方向，可以分成正向、反向动态规划：
从前往后（正向dp） vs 从后往前（反向dp）
- 从前往后（正向dp）[前文分析的就是这种思路]
cutNum[i] 表示字符串s从0到i结尾的字串所需要的最小分割数。
如果从j到i为回文的话： cutNum[i] = min( cutNum[i] , cutNum[j] + 1)
相应的，这种方向判断字符串中任意两个字串是否回文的区间dp为：
使用dp[i][j]， 为true则表示子字符串 s[j,i]是回文
当
(a) s[i] == s[j] && i-j < 2
或
(b) s[i]==s[j] && matrix[j+1][i-1] == true
时,matrix[i][j] = true
注意，(a) 必须放在(b)前面，否则程序运行到(b)会报越界错误。
具体代码：
public int minCut(String s) {
if(s==null || s.length() < 2)
return 0;
int[] cutNum = new int[s.length()];
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i=0; i<s.length(); i++)
{
cutNum[i] = i; // 最大切割数
for(int j=i; j>=0; j--)
{
if( (s.charAt(i)==s.charAt(j)) && ( (i-j<2)||(dp[j+1][i-1]==true) ))
{
dp[j][i] = true;
if(j==0)
cutNum[i] = 0; // 字符串 从0到i已经是回文了，不需要切割
else if(cutNum[j-1] + 1 < cutNum[i])
cutNum[i] = cutNum[j-1]+1;
}
}
}
return cutNum[s.length()-1];
}
注意： 在判断那里要先写 (i-j<2)再 || (dp[j+1][i-1]==true)，否则会越界
2.从后往前（反向dp） 的思路
从字符串后半部分开始考虑：
cutNum[i] 表示字符串 s 从 i 到末尾的子串所需要的最小分割数
如果从 i 到 j 的子串为回文串的话，那么最小分割数就可能为 j + 1以后的子串的最小分割数加上 j 和 j + 1 之间的一割。
状态转移方程为：
cutNum[i] = min(cutNum[i], cutNum[j + 1] + 1)
相应的，这种方向判断字符串中任意两个字串是否回文的区间dp为：
使用dp[i][j]， 为true则表示子字符串s[i,j]是回文
当
(a) s[i] == s[j] && i-j < 2 (字符为相邻字符或同一个位置的字符)
或
(b) s[i]]==s[j] && matrix[i+1][j-1] == true
时,matrix[i][j] = true;
注意，(a) 必须放在 (b)前面，否则程序运行到(b)会报越界错误
具体代码：
public int minCut(String s) {
if(s==null || s.length() < 2)
return 0;
int[] cutNum = new int[s.length()];
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i=s.length()-1; i>=0; i--)
{
cutNum[i] = s.length()-i-1;
for(int j=i; j<s.length(); j++)
{
if( (s.charAt(i) == s.charAt(j)) && ((j-i<2)||(dp[i+1][j-1]==true)) )
{
dp[i][j] = true;
if(j==s.length()-1)
cutNum[i] = 0;
else
cutNum[i] = Math.min(cutNum[i], cutNum[j+1]+1);
}
}
}
return cutNum[0];
}
参考：
http://blog.csdn.net/ljiabin/article/details/41173417
小收获
(1) 一个问题里面嵌套了两个dp的时候，要先找出大的dp, 然后找出小的dp
(2) dp的方向不一样的时候，要注意下标表示的是什么
(3) 多个循环判断条件放在一起的时候，要合理组合顺序
网友评论