Palindrome Continued
给定一个 String,考虑所有 substring / interval 的过程和 CLRS 中的 rod-cutting 是非常接近的,每一个可能的 substring 其实都只是下图中的某一段。大多数问题中 substring 的结构只会比 rod-cutting 更简单,比如只切一下,或者 rod 一定从最左端开始,etc.
在做 DP 之前,仔细思考状态转移方程与递推关系式(optimal substructure),尤其是求 min / max 的 DP,要认真考虑下到底最优解之间是不是“相邻”的。
判断一个 DP 结构的结果正确与否,要看从 base case 开始,每一次 update 的结构是否是正确解
LeetCode Hard 题。这题其实得到个能用的正确解不是难事,依照 Palindrome Patitioning I 的思路根据所有 substring 建个 dp 矩阵,然后递归也可以算,不过太慢了。在这种只要求返回最终解 int 的题里,一般都有比较妖孽的优化或者 dp,比较暴力的 divide & conquer 是不够的。
这个问题其实是在问,给定你一个 string ,虽少可以拆成几个 palindrome substring (减一).
试了几种超时/错误的解法之后,发现这题其实就是 rod cutting 的变种。
另一个尝试是直接 int[][] dp, 过了 20/28 个 test case,不过结果错误,挂在了 test case "ababbbabbaba" 上,应该返回3,这个代码返回1.
正确的minCut 是 aba|b|bbabb|aba
我的代码在检查"ababbb" 这个substring 的时候会出错,在看 a|(babbb) 的时候,我没考虑到其实 j 可以向右跳两步构造出最短的 palindrome. 目前的 DP 代码只假设了相邻一步的,导致结果不正确。
这个错误说明了:
在 Palindrome 中,依赖相邻字符的optimal substructure 只在 “某个子串是不是palindrome” 上有效。
在“最少子串数量”上,只检查相邻字符的 optimal substructure是有问题的,因为最优的 cut 可能在任意的其他位置,而不是相邻。
借鉴了论坛上的解法之后,能 AC 的代码如下:
这个代码其实是做了两个 DP. 一个是利用 palindrome substring 结构里合理的相邻 optimal substructure,构造出所有 substring 的 isPalindrome 矩阵;
另一个是关于 substring palindrome 数量的,虽然上一段代码已经说明了,我们不能只根据数量去推导 optimal substructure,因为给定 S, S + 'x' 的最优 cut 不一定相邻,因此破坏了 “相邻 optimal substructure” 的条件。
然而,如果已知 S 是 palindrome 的话,S + 'x' 一定不是 palindrome,这就是一个有效的“相邻 optimal substructure”.
在下面这段代码里,我们只有在已知一个 substring 是 palindrome 的情况下,才去利用这层递推关系式。
每一个 i 位置只会被更新一次,并且是正解,因为在每次 i 的循环中,我们检查了所有可能的 substring,并且在发现 palindrome 的情况下更新了当前 i 的最小值。
在每一个位置 i 上,左边都是之前的 dp 计算好的,右边都是在循环中自己检查的,每个位置的最优解是两段拼接的结果。
Last updated