Palindrome Continued

• 给定一个 String，考虑所有 substring / interval 的过程和 CLRS 中的 rod-cutting 是非常接近的，每一个可能的 substring 其实都只是下图中的某一段。大多数问题中 substring 的结构只会比 rod-cutting 更简单，比如只切一下，或者 rod 一定从最左端开始，etc.

  

• 在做 DP 之前，仔细思考状态转移方程与递推关系式（optimal substructure），尤其是求 min / max 的 DP，要认真考虑下到底最优解之间是不是“相邻”的。

• 判断一个 DP 结构的结果正确与否，要看从 base case 开始，每一次 update 的结构是否是正确解

Palindrome Partitioning II

LeetCode Hard 题。这题其实得到个能用的正确解不是难事，依照 Palindrome Patitioning I 的思路根据所有 substring 建个 dp 矩阵，然后递归也可以算，不过太慢了。在这种只要求返回最终解 int 的题里，一般都有比较妖孽的优化或者 dp，比较暴力的 divide & conquer 是不够的。

这个问题其实是在问，给定你一个 string ，虽少可以拆成几个 palindrome substring (减一).

试了几种超时/错误的解法之后，发现这题其实就是 rod cutting 的变种。

public class Solution {
    public int minCut(String s) {
        int n = s.length();
        if(n <= 1) return 0;

        boolean[][] dp = new boolean[n][n];

        for(int i = 0; i < s.length(); i++){
            for(int j = 0; j <= i; j++){
                if(s.charAt(i) == s.charAt(j) &&( i - j <= 2 || dp[i - 1][j + 1])){
                    dp[i][j] = dp[j][i] = true;
                }
            }
        }

        return getMinPieces(s, dp, 0, n - 1) - 1;
    }

    private int getMinPieces(String s, boolean[][] isPalindrome, int start, int end){
        if(start == end) return 1;
        if(isPalindrome[start][end]) return 1;

        int min = s.length();
        for(int i = start; i < end; i++){
        // 回头再看，这段其实就是未优化版的 dp 逻辑。
        // 把 left 替换成 dp[]，right 替换成 isPalindrome 就是 dp 了。
        // 再仔细思考下的话，每一对 index 的区间 [i , j] 
        // 其实在递归中重复出现了许多次，并且又满足 optimal substructure.
            int left = getMinPieces(s, isPalindrome, start, i);
            int right = getMinPieces(s, isPalindrome, i + 1, end);
            min = Math.min(min, left + right);
        }

        return min;
    }
}

另一个尝试是直接 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 可能在任意的其他位置，而不是相邻。

public class Solution {
    public int minCut(String s) {
        int n = s.length();
        if(n <= 1) return 0;

        int[][] dp = new int[n][n];

        for(int i = 0; i < s.length(); i++){
            for(int j = i; j >= 0; j--){
                if(s.charAt(i) == s.charAt(j)){
                    if(i - j < 2){
                        dp[i][j] = dp[j][i] = 1;
                    } else {
                        int middle = dp[i - 1][j + 1];
                        int left = dp[i - 1][j] + 1;
                        int right = dp[i][j + 1] + 1; 

                        dp[i][j] = dp[j][i] = Math.min(middle, Math.min(left, right));
                    }
                } else {
                    if(i - j < 2){
                        dp[i][j] = dp[j][i] = 2;
                    } else {
                        int middle = dp[i - 1][j + 1] + 2;
                        int left = dp[i - 1][j] + 1;
                        int right = dp[i][j + 1] + 1;

                        dp[i][j] = dp[j][i] = Math.min(middle, Math.min(left, right));
                    }
                }
            }
        }

        return dp[0][s.length() - 1] - 1;
    }
}

借鉴了论坛上的解法之后，能 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 计算好的，右边都是在循环中自己检查的，每个位置的最优解是两段拼接的结果。

public class Solution {
    public int minCut(String s) {
        if(s == null || s.length() <= 1) return 0;
        int len = s.length();

        boolean[][] isPalindrome = new boolean[len][len];
        int[] dp = new int[len];

        for(int i = 0; i < len; i++){
            dp[i] = i;
            for(int j = 0; j <= i; j++){
                if(s.charAt(i) == s.charAt(j) && (i - j < 2 || isPalindrome[j + 1][i - 1])){
                    isPalindrome[i][j] = isPalindrome[j][i] = true;
                    if(j == 0){
                        dp[i] = 0;
                    } else {
                        dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }

        return dp[len - 1];
    }
}