# Palindrome Continued

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

  ![](/files/-MUt7ZzFDAp2zELgTs5e)

![](/files/-MUt7ZzG3DeQ0RQEyJqU)

* **在做 DP 之前，仔细思考状态转移方程与递推关系式（optimal substructure），尤其是求 min / max 的 DP，要认真考虑下到底最优解之间是不是“相邻”的。**
* **判断一个 DP 结构的结果正确与否，要看从 base case 开始，每一次 update 的结构是否是正确解**

## [Palindrome Partitioning II](https://leetcode.com/problems/palindrome-partitioning-ii/)

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

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

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

```java
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 可能在任意的其他位置，而不是相邻。

```java
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 计算好的，右边都是在循环中自己检查的，每个位置的最优解是两段拼接的结果。**

```java
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];
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/stringff0c_zi_fu_chuan_lei/524_string-_palindrome_continued.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.