关于 L131 的 dp 解法的问题
来源：8-2 什么是回溯
Poplar_hills
2019-11-18
Hi bobo 老师，
我在解 L131 Palindrome Partitioning 时看到了一个很有意思的 dp 解法，代码如下：
int len = s.length();
List<List<String>>[] dp = new List[len + 1]; // dp[i] 记录 s[0..i] 上的解
boolean[][] palChecks = new boolean[len][len]; // palChecks[j][i] 记录 s[j..i] 是否是一个回文串
dp[0] = new ArrayList<List<String>>();
dp[0].add(new ArrayList<String>());
for (int i = 0; i < s.length(); i++) {
dp[i + 1] = new ArrayList<List<String>>();
for (int j = 0; j <= i; j++) {
if ((s.charAt(j) == s.charAt(i)) && (i - j <= 1 || palChecks[j + 1][i - 1])) { // 递推 s[j..i] 是否是 palindrome
palChecks[j][i] = true;
String str = s.substring(j, i + 1);
for (List<String> list : dp[j]) {
List<String> newList = new ArrayList<String>(list);
newList.add(str);
dp[i + 1].add(newList);
}
}
}
}
return dp[len];我理解这个解法中使用了两套 dp，目的是避免回溯法中的2处重复计算：
例如"aabb"中的"bb"会被重复切分成 ["b","b"]、["bb"] 两次；
对于每一次切分出来的子串，都要执行一次 isPalindrome(substr) 的检查，因此同样存在重复。
第二套 dp 比较好理解，状态转移方程应该就是 if 中的条件：
f(j, i) = (s[i] == s[j]) && (i - j <= 1 || f(j+1, i-1))
但是我实在没看懂第一套 dp 中是如何通过 dp[i] 递推出 dp[i+1] 的，因此也写不出状态转移方程。
因为之前已经学过第9章，但还是没能看懂这个解法，所以只能来向老师请教了
非常谢谢！
写回答
1回答
-
首先，你的注释有点儿问题：
// dp[i] 记录 s[0..i) 上的解。
i 是开区间。也可以理解成是前 i 个字符上的解。所以最终结果是 dp[len]
然后，核心是以下循环，我写成注释了：
// 之前的逻辑是，判断出了 s[j...i] 是一个回文串 // 此时，拿出 s[0...j) 上的所有解 for (List<String> list : dp[j]) { // 每一个 list，都是 s[0...j) 上的一个解 // newLiist 首先复制了这个解 List<String> newList = new ArrayList<String>(list); // 在 newList 中添加 s[j...i] // 此时 newList 就是 s[0...i + 1) 上的一个解了 newList.add(str); // 将这个解扔进 dp[i + 1] dp[i + 1].add(newList); }如果看了上面注释，理解不透彻的话，建议使用一个小的测试用例，具体跟踪一下，看看程序的每一步，各个变量在怎么变化，尤其是每一个 dp[x] 的列表里是怎么变化的。程序最终是怎么一步一步获得结果的？
继续加油！：）
012019-11-18
相似问题
DP+字符串的问题。。。
回答 1
关于校招dp难度的问题
回答 1