动态规划——回文串问题

练习1：回文子串

练习2：最长回文子串

练习3：回文串分割IV

练习4：分割回文串

练习5：最长回文子序列

练习6：让字符串成为回文串的最小插入次数

本篇文章主要学习使用动态规划来解决回文串相关问题，我们通过相关练习来学习

练习1：回文子串

题目链接：

647. 回文子串 - 力扣（LeetCode）

题目描述：

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

1 <= s.length <= 1000
s 由小写英文字母组成

思路分析：

题目要求我们统计字符串中 回文子串 的数目，其中，具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。如例2所示：

选择前两个位置的字符，形成子串 "aa"，选择后两个位置的字符，形成子串"aa"，这两个子串虽然字符相同，但其开始和结束位置不同，因此，视作不同的子串

子串：字符串中的由连续字符组成的一个序列。

我们来分析状态表示

状态表示：

要统计字符串中回文子串的个数，就是要判断字符串的所有子串是否回文，如何判断呢？

要判断子串是否是回文，首先要找到所有子串，

表示出所有子串

我们以 i 位置作为子串的起始位置，j 位置作为子串的结束位置

我们固定 i 位置，然后向后移动 j 位置，就可以枚举出以 i 位置为起始的所有子串

然后向后移动 i，继续向后枚举

因此，我们使用两层 for 循环，就可以枚举出字符串的所有子串，也就是说，我们用一个二维数组就可以表示出所有情况

我们以横坐标作为子串的起始位置，纵坐标作为子串的结束位置：

dp[i][j]：以 i 位置为起始，j 位置为结束的子串

由于起始位置 <= 结束位置，因此，我们只需要使用dp表中右上三角部分的空间就可以表示出所有子串

接下来，我们判断子串是否是回文串

判断子串是否是回文串

我们已经使用二维dp表表示出了所有情况，因此，我们只需要想办法在对应[i, j]位置上填上 true 或 false，就可以表示以 i 位置为起始，j位置为结束的字符是否是回文串了

因此，dp[i][j]：以 i 位置为起始，j位置为结束的子串是否是回文串

状态转移方程：

要判断子串（从i位置到j位置）是否是回文串，首先要判断两端点（s[i] == s[j]）是否相同，

若两端的字符都不相同，则子串一定不是回文串

若两端点相同，我们还需分情况讨论：

若 i = j，则该子串只有一个字符，一定是回文串，dp[i][j] = true

若 i + 1 = j，该子串有两个字符且相同，一定是回文串，dp[i][j] = true

若 i + 1 < j，则该子串有多个字符，我们已经判断出两端点的字符相同，接下来，我们需要判断 [i+1, j-1]区间内的字符是否相同，即判断以 i + 1位置为起始，j - 1位置为结束的子串是否是回文串

而 dp[i+1][j-1] 表示以 i + 1位置为起始，j - 1位置的子串是否是回文串，因此 dp[i][j] = dp[i+1][j-1]

因此，状态转移方程为：

初始化：

初始化要保证填表时不越界，但在填写dp表时，不会发生越界，因此我们无需初始化

填表顺序：

当 s[i] = s[j] 且 i + 1 < j 时，dp[i][j] = dp[i+1][j-1]

因此，在填写 [i][j]位置时要保证[i+1][j-1]位置已经填写，因此，需要从下往上填写，而在填写每一行时，从左往右或从右往左都可以

返回值：

要求回文子串的个数，因此，要返回 dp 表中 true 的个数

代码实现：

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int ret = 0;//统计回文子串的个数
        //创建dp表
        boolean[][] dp = new boolean[n][n];
        //初始化
        //填表
        for(int i = n - 1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(i == j || i + 1 == j) dp[i][j] = true;
                    else dp[i][j] = dp[i + 1][j - 1];
                }
                if(dp[i][j]) ret++;
            }
        }
        //返回
        return ret;
    }
}

练习2：最长回文子串

题目链接：

5. 最长回文子串 - 力扣（LeetCode）

题目描述：

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

思路分析：

题目要求我们找到字符串中的最长回文子串。因此，我们首先要判断子串是否是回文串，然后再找到其中最长的回文子串

本题的解题思路与 练习1：回文子串 类似

我们可以使用二维dp表表示出所有情况，判断出所有子串是否为回文串

若 dp[i][j] = true，则以 i 位置为起始，j 位置为结尾的子串是回文串，其长度为 j - i + 1

因此，我们只需找到回文子串中 j - i + 1 的最大值，即可找到最长的回文子串

代码实现：

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int begin = 0, len = 1;//记录最长子串的起始位置和长度
        //创建dp表
        boolean[][] dp = new boolean[n][n];
        //初始化
        //填表
        for(int i = n - 1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
                if(dp[i][j] && j - i + 1 > len){
                    len = j - i + 1;
                    begin = i;
                }
            }
        }
        //返回
        return s.substring(begin, begin + len);
    }
}

练习3：回文串分割IV

题目链接：

1745. 分割回文串 IV - 力扣（LeetCode）

题目描述：

给你一个字符串 s ，如果可以将它分割成三个非空回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

示例 1：

输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。

示例 2：

输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。

提示：

3 <= s.length <= 2000
s 只包含小写英文字母。

思路分析：

将字符串分割成三个非空字符串，若分割后三个子串都是回文串，则返回true，不能分割，则返回false

设中间字符串的起始位置为 i，结束位置为 j

则划分后三个子串的区间分别为：[0, i - 1] [i, j] [j + 1, n-1]

此时，我们需要判断三个子串是否是回文串

同样的，我们可以使用二维dp表表示出所有情况，判断出所有子串是否为回文串

此时，判断这三个子串是否是回文串就变得非常简单了，只需判断 dp[0][i - 1]、dp[i, j] 和 dp[j + 1][n - 1] 是否都为true，就可以判断出这三个子串是否都是回文串了

因此，只需先判断所有子串是否是回文串，然后枚举第二个字符串所有的起始位置和结束位置，查询这三段非空子串是否是回文串即可

代码实现：

class Solution {
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        //判断所有子串是否是回文串
        for(int i = n - 1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(s.charAt(i) == s.charAt(j)) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
            }
        }
        //枚举第二个字符串的所有起始位置和结束位置
        for(int i = 1; i < n - 1; i ++){
            for(int j = i; j < n - 1; j++){
                if(dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]) return true;
            }   
        }
        return false;
    }
}

练习4：分割回文串

题目链接：

132. 分割回文串 II - 力扣（LeetCode）

题目描述：

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成

思路分析：

要求将字符串分割成子串的最少分割次数

状态表示：

我们首先以 i 位置为结尾进行分析：

则 dp[i]： [0, i]区间内的最少分割次数

状态转移方程：

若以 0 位置为起始，i位置为结尾的子串是回文串，此时不需要分割，dp[i] = 0

而以 0 位置为起始，i位置为结尾的子串不是回文串时，我们根据前面的状态来推导 dp[i]

假设我们在 j 位置进行分割，则分割出以 j 位置为起始，i 位置为结尾的子串，若这个子串是回文串

则我们只需要考虑 [0, j - 1]区间内分割了多少词（dp[j - 1]），再加上这一次，就可以得到 dp[i]

因此，我们先考虑最后一次分割：

假设在 j 位置进行分割（0 < j <= i），然后判断从 j 到 i 这个子串是否是回文串：

若是回文串，则 dp[i] = dp[j - 1] + 1

若不是回文串，此时这种分割方式不合理，不考虑

我们要求最小分割次数，因此我们要求能够分割的情况中的最小值（即min(dp[j - 1] + 1)）

在此过程中，我们需要判断 [0, i ] 区间子串是否是回文，[j, i]区间子串是否是回文，因此，我们同样可以使用二维dp表，判断所有子串是否是回文串

初始化：

初始化要保证填表时不越界，当 j = 0时可能会越界，但 j 不可能为 0，因此不会发生越界，但由于我们要求 dp[i]的最小值，因此我们可以将所有的值都初始化为最大值

填表顺序：

填写 dp[i] 时，要保证 dp[j - 1]已经填写，j - 1 在 i 位置之前，因此填表顺序为从左到右

返回值：

dp[i] ：0 到 i 位置的最小分割次数，要求字符串的最小分割次数，因此返回 dp[n - 1]

代码实现：

class Solution {
    public int minCut(String s) {
        //预处理
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];
        for(int i = n - 1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(s.charAt(i) == s.charAt(j)) isPal[i][j] = i + 1 < j ? isPal[i + 1][j - 1] : true;
            }
        }
        //创建dp表
        int[] dp = new int[n];
        //初始化
        for(int i = 0; i < n; i++) dp[i] = Integer.MAX_VALUE;
        //填表
        for(int i = 0; i < n; i++){
            if(isPal[0][i]) dp[i] = 0;
            else{
                for(int j = 1; j <= i; j++){
                    if(isPal[j][i]) dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }
        //返回
        return dp[n - 1];
    }
}

练习5：最长回文子序列

题目链接：

516. 最长回文子序列 - 力扣（LeetCode）

题目描述：

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

思路分析：

本题与前面的题不同，要求的是最长回文序列，子串，是连续的字符串，而子序列，可以是连续的，也可以是不连续的，是在不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

状态表示：

我们首先以 i 位置为结尾进行分析，则 dp[i]：以 i 位置为结尾的所有子序列中，最长的回文子序列的长度

接着，我们来分析状态转移方程：

我们需要根据前面的状态来推导dp[i]，我们以 i - 1位置进行分析，但是 dp[i - 1] ：以 i 位置为结尾的所有子序列中，最长的回文子序列的长度，我们不知道回文子序列是怎样的，不能确定添加s[i]后是否依旧是回文子序列，因此无法确定dp[i]

我们再考虑其他方法

若以 i 位置为起始，j 位置为结尾的子串是回文串，在这个子串的左右加上相同的字符，新的子串依旧是回文串

则，若[i + 1, j - 1]内存在最长回文子序列，则

若s[i] == s[j]，则最长回文子序列长度 + 2，则[i, j]区间内的最长回文子序列长度 = [i + 1, j - 1]区间内最长回文子序列长度 + 2，因此我们可以根据[i+1, j - 1]区间内的最长回文子序列长度，推导出[i, j]区间内最长回文子序列的长度

我们根据这个思路来定义状态表示：

dp[i][j]：字符串[i, j]区间内的最长回文子序列长度

接下来，我们分析状态转移方程

状态转移方程：

我们以 i 位置为起始，j 位置为结束

若 s[i] = s[j]，则 dp[i][j] = dp[i + 1][j - 1] + 1，但前提条件是dp[i + 1][j - 1]存在，因此，我们需要分情况讨论：

若 i = j，则[i, j]区间内只有一个字符，则最长回文子序列长度为 1

若 i + 1 = j，则[i, j]区间内有两个相同的字符，则最长回文子序列长度为 2

若 i + 1 < j，则[i, j]区间内有多个字符，则只需要在[i + 1, j - 1]区间内找到最长回文子序列长度，然后再 + 2，即 dp[i + 1][j - 1] + 2

若 s[i] != s[j]，则最长回文子序列一定不可能以 i 位置为起始，以 j 位置为结束，因此，我们可以在[i, j - 1]内找最长回文子序列长度，然后在[i + 1, j]区间内找最长回文子序列长度，最后取其中的较大值，即 max(dp[i, j - 1], dp[i + 1, j])

因此，状态转移方程为：

初始化：

由于在填表时不会发生越界，因此无需初始化

填表顺序：

由于 i <= j，因此只会填写：

在填写dp[i][j]时，需要 dp[i + 1][j - 1]、dp[i][j - 1] 和 dp[i - 1][j]

因此，我们首先要保证从下往上填写，在填写时需要用到左边的值，因此在填写每一行时，要从左往右填写

返回值：

dp[i][j]：字符串[i, j]区间内的最长回文子序列长度，而需要求字符串的最长回文子序列长度，即起始位置为0，结束位置为 n - 1，因此，返回dp[0][n - 1]

代码实现：

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        //创建dp表
        int[][] dp = new int[n][n];
        //初始化
        //填表
        for(int i = n - 1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(i == j) dp[i][j] = 1;
                    else if(i + 1 == j) dp[i][j] = 2;
                    else dp[i][j] = dp[i + 1][j - 1] + 2;
                }else{
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
                
            }
        }
        //返回
        return dp[0][n - 1];
    }
}

练习6：让字符串成为回文串的最小插入次数

题目链接：

1312. 让字符串成为回文串的最少插入次数 - 力扣（LeetCode）

题目描述：

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

示例 1：

输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。

示例 2：

输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

示例 3：

输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。

提示：

1 <= s.length <= 500
s 中所有字符都是小写字母。

思路分析：

题目要求我们在字符串中插入字符使其成为回文串，要求出最少插入次数

状态表示：

与 练习5：最长回文子序列 类似，当我们选择以 i 位置为结尾时，很难推出状态转移方程，因此，我们以 [i, j]区间来研究问题（i <= j）

dp[i][j]：[i, j]区间内，使其成为回文串的最小插入次数

状态转移方程：

我们根据最后一步来划分问题，也就是根据两个端点（i，j）来划分问题：

若 s[i] = s[j]：

若 i = j，则[i, j]区间内只有一个字符，此时已经是回文串了，插入次数为0

若 i + 1 = j，则[i, j]区间内有两个字符相同的字符，此时也是回文串了，插入次数为 0

若 i + 1 < j，则[i, j]区间内有多个字符，由于s[i] = s[j]，因此两端字符不用考虑，只需考虑[i + 1, j - 1]区间内的最小插入次数，即 dp[i + 1][j - 1]

若 s[i] != s[j]：

此时我们在[i, j]区间的最左边添加上字符s[j]，就可以与最右边的s[j]匹配，此时，我们只需考虑[i, j - 1]区间内的最小操作次数，即 dp[i][j - 1]，然后再加上此时添加的一个字符，即 dp[i][j - 1] + 1

同样的，在最右边添加上字符s[i]，就可以和最左边的s[i]匹配，此时只需考虑[i + 1, j]区间内的最小操作次数，即 dp[i + 1][j]，然后再加上此时添加的一个字符，即 dp[i + 1][j] + 1

要最小操作次数，只需取最小值，min(dp[i + 1][j] + 1, dp[i][j - 1] + 1)

因此，状态转移方程为：

初始化： 由于在填表时不会发生越界，因此无需初始化

填表顺序：

在填写dp[i][j]时，需要 dp[i + 1][j - 1]、dp[i][j - 1] 和 dp[i - 1][j]

因此，我们首先要保证从下往上填写，在填写时需要用到左边的值，因此在填写每一行时，要从左往右填写

返回值：

dp[i][j]：[i, j]区间内，使其成为回文串的最小插入次数，而需要求字符串成为回文串的最少插入次数，即起始位置为0，结束位置为 n - 1，因此，返回dp[0][n - 1]

代码实现：

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        //创建dp表
        int[][] dp = new int[n][n];
        //填表
        for(int i = n-1; i >= 0; i--){
            for(int j = i + 1; j < n; j++){//i = j的时候,dp[i][j] = 0,因此无需再考虑
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i][j - 1] + 1, dp[i + 1][j] + 1);
                }
            }
        }
        //返回
        return dp[0][n - 1];
    }
}