动态规划-子序列问题（判断子序列、不同的子序列、两个字符串的删除操作、编辑距离、回文子串、最长回文子序列）

清疚 2023-09-25 21:17 9阅读 0赞

#### 文章目录 ####

*  1. 判断子序列
 *   *   *  思路：
         *  代码：
 *  2. 不同的子序列
 *   *   *  思路：
         *  代码：
 *  3. 两个字符串的删除操作
 *   *   *  思路：
         *  代码：
 *  4. 编辑距离
 *   *   *  思路：
         *  代码：
 *  5. 回文子串
 *   *   *  思路：
         *  代码：
 *  6. 最长回文子序列
 *   *   *  思路：
         *  代码：

## 1. 判断子序列 ##

**题目链接：**[392. 判断子序列 - 力扣（LeetCode）][392. _ - _LeetCode]

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

**示例 1：**

> 输入：s = “abc”, t = “ahbgdc”  
> 输出：true

**示例 2：**

> 输入：s = “axc”, t = “ahbgdc”  
> 输出：false

**提示：**

*  0 <= s.length <= 100
 *  0 <= t.length <= 10^4
 *  两个字符串都只由小写字符组成。

#### 思路： ####

本道题是编辑距离的入门题目，题目只需要计算删除的情况，不用考虑增加和替换的情况。

**下面用动归五部曲分析一下**

1.  状态定义：dp\[i\] \[j\] 表示：以下标 i-1 为结尾的字符串 S，和以下标 j-1 为 结尾的字符串 t，相同子序列的长度为 dp\[i\] \[j\]。
    
    这样定义的目的是想 dp 推导的最后，只要和 s 长度相等，那么 s 肯定就是 t 的子序列，返回 true 就可以了。
    
    定义下标为 i-1 和 j-1 的目的是为了方便初始化。如果直接定义 i 和 j，比如 dp\[i\] \[0\] 的初始化，当 i = 0 时，和 s 第一个元素相等时就要初始化，每次都要比较来进行初始化。而定义下标 i-1 和 j-1 的好处就是，初始化是在后面递推公式中初始化的，不用额外判断，遍历时只要 s 和 t 的从第二元素开始遍历即可。
2.  状态转移：
    
        if (s[i-1] == t[j-1]) // t 中的一个元素在 s 中也存在
        	dp[i][j] = dp[i-1][j-1] + 1  // 因为找到一个相同的字符，所以子序列长度就要在 dp[i-1][j-1] 的基础上加 1
        if (s[i-1] != t[j-1]) // 此时 t 中的这个元素在 s 中不存在，那么删除 t 中的这个元素，也就是要删除元素 t[j-1]，那么 dp[i][j] 的值就是要看 s[i-1] 与 t[j-2] 的比较结果（是否一样），
        	dp[i][j] = dp[i][j-1]
    
    **需要注意本道题是只有 t 可以删除**
3.  初始化：分析递推公式，dp\[i\] \[j\] 依赖 dp\[i-1\] \[j-1\] 和 dp\[i\] \[j-1\]，所以 dp\[0\] \[0\] 和 dp\[i\] \[0\] 一定要要初始化。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VzASfYI1-1680432158238)(C:\\Users\\28463\\AppData\\Roaming\\Typora\\typora-user-images\\1680229780552.png)\]][img-VzASfYI1-1680432158238_C_Users_28463_AppData_Roaming_Typora_typora-user-images_1680229780552.png]

1.  遍历顺序：从上到下，从左到右
2.  返回值：dp\[s.length()\] \[t.length()\]

#### 代码： ####

/**
        1. 状态定义：dp[i] [j] 表示：以下标 i-1 为结尾的字符串 S，和以下标 j-1 为 结尾的字符串 t，相同子序列的长度为 dp[i] [j]
        2. 状态转移：if (s[i-1] == t[j-1]) 
        dp[i][j] = dp[i-1][j-1] + 1
         if (s[i-1] != t[j-1]) 
         	dp[i][j] = dp[i][j-1]
        3. 初始化：0
        4. 遍历顺序：从上到下，从左到右
        5. 返回值：dp[s.length()] [t.length()]
         */
        public boolean isSubsequence(String s, String t) {
        
            int s1 = s.length();
            int t1 = t.length();
            int[][] dp = new int[s1+1][t1+1];
            for(int i = 1; i <= s1; i++) {
        
                for(int j = 1; j <= t1; j++) {
        
                    if(s.charAt(i-1) == t.charAt(j-1)) {
        
                        dp[i][j] = dp[i-1][j-1]+1;
                    } else {
        
                        dp[i][j] = dp[i][j-1];
                    }
                }
            }
            boolean ret = dp[s1][t1] == s1 ? true : false;
            return ret;
        }

## 2. 不同的子序列 ##

**题目链接：**[115. 不同的子序列 - 力扣（LeetCode）][115. _ - _LeetCode]

给定一个字符串 s 和一个字符串 t ，**计算在 s 的子序列中 t 出现的个数**。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

**示例 1：**

> 输入：s = “rabbbit”, t = “rabbit”  
> 输出：3  
> 解释：  
> 如下图所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。  
> rabbbit  
> rabbbit  
> rabbbit

**示例 2：**

> 输入：s = “babgbag”, t = “bag”  
> 输出：5  
> 解释：  
> 如下图所示, 有 5 种可以从 s 中得到 “bag” 的方案。  
> babgbag  
> babgbag  
> babgbag  
> babgbag  
> babgbag

**提示：**

*  0 <= s.length, t.length <= 1000
 *  s 和 t 由英文字母组成

#### 思路： ####

上一题是判断 s 是否是 t 的子序列，而本道题是计算在 s 的子序列中 t 出现的个数（有子序列了，然后要统计个数）

**继续用动归五部曲分析**

1.  状态定义：dp\[i\] \[j\] 表示：以 i-1 为结尾 s 子序列中有以 j-1 为结尾的 t 的个数为 dp\[i\] \[j\]
    
    这里定义 i-1 和 j-1 是为了方便初始化。
2.  状态转移：

有两种情况：

*  **s\[i-1\] 和 t\[j-1\] 相等** dp\[i\] \[j\] = dp\[i-1\] \[j-1\] + dp\[i-1\] \[j\]
    
    相等时 dp\[i\] \[j\] 由两个部分组成
    
    一部分是 s\[i-1\] 参与匹配，那么就是用 s 中 0 到 i-2 个字符去匹配 t 中的 0 到 j-2 字符，此时匹配的值就是 dp\[i-1\] \[j-1\]
    
    一部分是 s\[i-1\] 不参与匹配，那么就是用 s 中 0 到 i-2 个字符去匹配 t 中的 0 到 j-1 字符，此时匹配的值就是 dp\[i-1\] \[j\]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LKeXYiZE-1680432158239)(C:\\Users\\28463\\AppData\\Roaming\\Typora\\typora-user-images\\1680243888639.png)\]][img-LKeXYiZE-1680432158239_C_Users_28463_AppData_Roaming_Typora_typora-user-images_1680243888639.png]

*  **s\[i-1\] 和 t\[j-1\] 不相等** dp\[i\] \[j\] = dp\[i-1\] \[j\]

那么就不用 s\[i-1\] 来匹配了，相当于模拟在 s 中删除这个元素

1.  初始化：可以从上面的图中看出来 dp 是由左上方和上方推导出来的，所以dp\[i\] \[0\] 和 dp\[0\] \[j\] 要初始化
    
     *  dp\[i\] \[0\] 表示以 i-1 为结尾的 s 可以随便删除元素，出现空字符串的个数
    
    所以 dp\[i\] \[0\] = 1，可以把 s 中所有元素删除，这样空字符串个数就是 1
    
     *  dp\[0\] \[j\] 表示 空字符串 s 可以随便删除元素，出现以 j-1 为结尾的字符串 t 的个数，所以 dp\[0\] \[j\] = 0
     *  dp\[0\] \[0\] = 1 因为空字符串 s ，可以删除 0 个元素就变成空字符串 t
2.  遍历顺序：从上到下，从左到右
3.  返回值：dp\[s.length()\] \[t.length()\]

#### 代码： ####

/**
        1. 状态定义：dp[i][j] 表示：以 i-1 为结尾  s 子序列中有以 j-1 为结尾的 t 的个数为 dp[i][j]
        2. 状态转移：s[i-1] 和 t[j-1] 相等 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    s[i-1] 和 t[j-1] 不相等 dp[i][j] = dp[i-1][j]
        3. 初始化： dp[i][0] = 1  dp[0][0] = 1 
        4. 遍历顺序：从上到下，从左到右
        5. 返回值：dp[s.length()][t.length()]
         */
        public int numDistinct(String s, String t) {
        
            int s1 = s.length();
            int t1 = t.length();
            int[][] dp = new int[s1+1][t1+1];
            // 初始化
            for(int i = 0; i < s1; i++) {
        
                dp[i][0] = 1;
            }
            // 遍历
            for(int i = 1; i <= s1; i++) {
        
                for(int j = 1; j <= t1; j++) {
        
                    if(s.charAt(i-1) == t.charAt(j-1)) {
        
                        dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                    } else {
        
                        dp[i][j] = dp[i-1][j];
                    }
                }
            }
            return dp[s1][t1];
        }

## 3. 两个字符串的删除操作 ##

**题目链接：**[583. 两个字符串的删除操作 - 力扣（LeetCode）][583. _ - _LeetCode]

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符

**示例 1：**

> 输入: word1 = “sea”, word2 = “eat”  
> 输出: 2  
> 解释: 第一步将 “sea” 变为 “ea” ，第二步将 "eat "变为 “ea”

**示例 2:**

> 输入：word1 = “leetcode”, word2 = “etco”  
> 输出：4

**提示：**

*  1 <= word1.length, word2.length <= 500
 *  word1 和 word2 只包含小写英文字母

#### 思路： ####

在上一题 不同的子序列中 是只能删除一个字符串，然后取匹配；而本道题是两个字符串都可以删除，大体思路和上一题是一样的，就是多考虑一种情况。

两个字符串互相可以删除，还是使用动态规划来解决。

**下面进行动归五部曲分析**

1.  状态定义：以 i-1 结尾的 word1 和 j-1 为结尾的 word2 转换为相同的序列最少的操作次数为 dp\[i\] \[j\]
2.  状态转移：
    
     *  当 word1\[i-1\] == word2\[j-1\] 时， 当前元素相同那么最少操作次数，和上一次是一样的，所以 dp\[i\] \[j\] = dp\[i-1\] \[j-1\]
     *  当 word1\[i-1\] != word2\[j-1\] 时，因为两个字符串都可以删除了，所以就有三种情况了
        
        1）删除 word1\[i-1\] 元素，那么要取 dp\[i-1\] \[\] 对应过来就是 word1\[i-2\] 就是不考虑 word1\[i-1\] 元素，然后操作次数 +1. 也就是 dp\[i-1\] \[j\] + 1
        
        2）删除 word2\[j-1\] 元素，同理， dp\[i\] \[j-1\] + 1
        
        3）删除 word1\[i-1\] 和 word2\[j-1\] 元素，操作次数为 dp\[i-1\] \[j-1\] + 2
    
    然后取这三种情况中最小值 dp\[i\] \[j\] = Math.min(dp\[i-1\] \[j\]+1,dp\[i\] \[j-1\]+1,dp\[i-1\] \[j-1\]+2)

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RMrkQVUS-1680432158239)(C:\\Users\\28463\\AppData\\Roaming\\Typora\\typora-user-images\\1680351377996.png)\]][img-RMrkQVUS-1680432158239_C_Users_28463_AppData_Roaming_Typora_typora-user-images_1680351377996.png]

1.  初始化：从这个图中可以看出来，dp\[i\] \[j\] 是由这三个方向推导出来的。
    
    所以 dp\[i\] \[0\] 和 dp\[0\] \[j\] 是一定要初始化的
    
    dp\[i\] \[0\] 表示 word2 为空字符串，以 i-1 为结尾的字符串 word1 要删除多少个元素，才能和 word2 相同，所以 dp\[i\] \[0\] = i （注意前面的 i-1 为下标，这里的 i 为操作次数）
    
    同理 dp\[0\] \[j\] = j
2.  遍历顺序：从上到下，从左到右
3.  返回值：dp\[word1.length()\] \[word2.length()\]

#### 代码： ####

/**
        1. 状态定义：以 i-1 结尾的 word1 和 j-1 为结尾的 word2 转换为相同的序列最少的操作次数为 dp[i][j]
        2. 状态转移：if(word1.charAt(i-1) == word2.charAt(j-1))
        dp[i][j] = dp[i-1][j-1];
        else dp[i][j] = Math.min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+2) // 删除当前 word1 元素，dp取[i-1]相当于 word 取 i-2，然后删除这个元素就+1 
        3. 初始化：dp[i][0]=i;dp[0][j]=j
        4. 遍历顺序：从小到大
        5. 返回值：dp[word1.length()][word2.length()]
         */
        public int minDistance(String word1, String word2) {
        
            int w1 = word1.length();
            int w2 = word2.length();
            int[][] dp = new int[w1+1][w2+1];
            // 初始化
            for(int i = 0; i <= w1; i++) {
        
                dp[i][0] = i;
            }
            for(int j = 0; j <= w2; j++) {
        
                dp[0][j] = j;
            }
            // 遍历
            for(int i = 1; i <= w1; i++) {
        
                for(int j = 1; j <= w2; j++) {
        
                    if(word1.charAt(i-1) == word2.charAt(j-1)) {
        
                        dp[i][j] = dp[i-1][j-1];
                    } else {
        
                        dp[i][j] = Math.min(dp[i-1][j-1]+2,Math.min(dp[i][j-1]+1,dp[i-1][j]+1));
                    }
                }
            }
            return dp[w1][w2];
        }

**这里还有一个思路就是，这个虽然说是求两个字符串的删除操作的最少次数，本质上还是找这个最长公共子串，所以本道题可以换一种思路就是，这个最小次数就等于，求这两个字符串长度之和 然后 减去这两个字符串的最大公共子串的2倍，这个步骤之后不就得到了那个最少操作的次数，就将两个字符串转化为一样的了**

// 1. 先通过 dp 找最长公共子串
        // 2. 要将两个字符串变为相同的最少操作次数 = w1 + w2 - dp*2;
        public int minDistance(String word1, String word2) {
        
            int w1 = word1.length();
            int w2 = word2.length();
            int[][] dp = new int[w1+1][w2+1];
            for(int i = 1; i <= w1; i++) {
        
                for(int j = 1; j <= w2; j++) {
        
                    if(word1.charAt(i-1) == word2.charAt(j-1)) {
        
                        dp[i][j] = dp[i-1][j-1] + 1;
                    } else {
        
                        dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                    }
                }
            }
            return w1+w2-dp[w1][w2]*2;
        }

## 4. 编辑距离 ##

**题目链接：**[72. 编辑距离 - 力扣（LeetCode）][72. _ - _LeetCode]

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符  
删除一个字符  
替换一个字符

**示例 1：**

> 输入：word1 = “horse”, word2 = “ros”  
> 输出：3  
> 解释：  
> horse -> rorse (将 ‘h’ 替换为 ‘r’)  
> rorse -> rose (删除 ‘r’)  
> rose -> ros (删除 ‘e’)

**示例 2：**

> 输入：word1 = “intention”, word2 = “execution”  
> 输出：5  
> 解释：  
> intention -> inention (删除 ‘t’)  
> inention -> enention (将 ‘i’ 替换为 ‘e’)  
> enention -> exention (将 ‘n’ 替换为 ‘x’)  
> exention -> exection (将 ‘n’ 替换为 ‘c’)  
> exection -> execution (插入 ‘u’)

**提示：**

*  0 <= word1.length, word2.length <= 500
 *  word1 和 word2 由小写英文字母组成

#### 思路： ####

前面的几道题都是为这道 编辑距离 做铺垫，还是用动态规划来做

**下面进行动归五部曲分析**

1.  状态定义：dp\[i\] \[j\] 表示以下标 i-1 为结尾的字符串 word1，和以下标 j-1 为结尾的字符串 word2，要转化为相同的字符串最少的操作次数是 dp\[i\] \[j\]。
2.  状态转移：
    
    **当 word1\[i-1\] == word2\[i-2\] 时**，不用进行任何操作，当前的最少操作次数就是上一次的 dp，也就是 dp\[i-1\] \[j-1\]，所以 **dp\[i\] \[j\] = dp\[i-1\] \[j-1\]**
    
    **当 word\[i-1\] != word2\[j-1\] 时**，此时就需要操作了，通过 增、删、改让元素相等。
    
    先看**删除**操作
    
    两个元素不相等，如果删除 word1 元素，那么就是以下标 i-2 为结尾的 word1 与 j-1 为结尾的 word2 的最少操作次数+1，即 **dp\[i-1\] \[j\] + 1**
    
    如果删除 word2 元素，那么就是以下标 i-1 为结尾 word1 与 j-2 为结尾的 word2 的最少操作次数+1，即 **dp\[i\] \[j-1\] + 1**
    
    下面看**添加**操作
    
    比如 word1 = “ad”， word2 = “a”，给 word2 添加元素 d，和 给 word1 删除 元素 d，让两个字符串变为一样的操作次数是相同的，所以 **添加操作和删除操作是一样**
    
    最后看**替换**操作
    
    当前 word1 和 word2 的两个元素不相同，只需要修改这两个元素中任意一个元素和另一个元素相同就可以了，这个只需要操作一次，但这个是在 dp\[i-1\] \[j-1\] 的基础上操作一次，即 **dp\[i-1\] \[j-1\] +1**
    
    **取这三种情况中最小的 dp\[i\] \[j\] = Math.min(dp\[i- 1\] \[j\]+1,Math.min(dp\[i\] \[j-1\]+1,dp\[i-1\] \[j-1\]+1))**
3.  初始化：
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dKUqrPVd-1680432158240)(C:\\Users\\28463\\AppData\\Roaming\\Typora\\typora-user-images\\1680351377996.png)\]][img-dKUqrPVd-1680432158240_C_Users_28463_AppData_Roaming_Typora_typora-user-images_1680351377996.png]
    
    可以看到 dp 是由这三个方向推导出来的，所以应该初始化 dp\[i\] \[0\] 和 dp\[0\] \[j\]。
    
    dp\[i\] \[0\] 应该初始化为 i，因为此时表示以下标 i-1 为结尾的 word1，和 空字符串 word2，转化为相同的最少操作次数，比如 i 为 1 时，此时就是在初始化 dp\[1\] \[0\] ，也就是 word1 以下标为 0 的字符结尾，转化为 word2 空字符串的最少操作次数为 1，所以 dp\[i\] \[0\] = i，同理 dp\[0\] \[j\] = j
4.  遍历顺序：从上到下，从左到右（从小到大）
5.  返回值： dp\[word1.length()\] \[word2.length()\]

#### 代码： ####

public int minDistance(String word1, String word2) {
        
            int w1 = word1.length();
            int w2 = word2.length();
            int[][] dp = new int[w1+1][w2+1];
            // 初始化
            for(int i = 0; i <= w1; i++) {
        
                dp[i][0] = i;
            }
            for(int j = 0; j <= w2; j++) {
        
                dp[0][j] = j;
            }
            // 遍历
            for(int i = 1; i <= w1; i++) {
        
                for(int j = 1; j <= w2; j++) {
        
                    if(word1.charAt(i-1) == word2.charAt(j-1)) {
        
                        dp[i][j] = dp[i-1][j-1];
                    } else {
        
                        dp[i][j] = Math.min(dp[i-1][j]+1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]+1));
                    }
                }
            }
            return dp[w1][w2];
        }

## 5. 回文子串 ##

**题目链接：**[647. 回文子串 - 力扣（LeetCode）][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 由小写英文字母组成

#### 思路： ####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rBKGo1o6-1680432158240)(C:\\Users\\28463\\AppData\\Roaming\\Typora\\typora-user-images\\1680421461589.png)\]][img-rBKGo1o6-1680432158240_C_Users_28463_AppData_Roaming_Typora_typora-user-images_1680421461589.png]

所以 dp 数组要定义为一个二维 dp 数组

1.  状态定义：布尔类型的 dp\[i\] \[j\]表示：在区间 \[i, j\] 的 子串是否是回文子串，如果是 dp\[i\] \[j\] = true，如果不是 dp\[i\] \[j\] = false
2.  状态转移：有两种情况
    
    s\[i\] != s\[j\] ，那么 dp\[i\] \[j\] 肯定不是回文子串，即 dp\[i\] \[j\] = false;
    
    s\[i\] == s\[j\]，又分为三种情况
    
     *  下标 i == j，那么就是 i 和 j 指向的是同一个字符，所以肯定是回文子串
     *  下标 i 和 j 相差1，也就是 i 和 j 是相邻的，两个相邻的元素相同，那肯定是回文子串
     *  下标 i 和 j 相差大于1，就是上面图中的情况，区间 \[i, j\] 是不是回文子串要看区间 \[i+1, j-1\] 是不是回文子串
    
        if(s[i] == s[j]) {
              
        	if(j-i <= 1) {
               // 指向同一个元素 或 指向的两个元素相邻
        		dp[i][j] = true;
        		result++; // 统计回文子串的数量
        	} else if(dp[i+1][j-1]) {
                // 要看 dp[i][j] 是否是回文，就要判断 dp[i+1][j-1] 的情况
        		dp[i][j] = true;
        		result++;
        	}
        } 
        // 这里 不用再判断 s[i] != s[j] 是因为这个肯定不是回文子串，没必要在判断了，初始化时直接 false
3.  初始化：dp\[i\] \[j\] 都要初始化为 false，这样状态转移方程经过判断后才修改为 true。
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TOmMARL9-1680432158241)(C:\\Users\\28463\\AppData\\Roaming\\Typora\\typora-user-images\\1680422275044.png)\]][img-TOmMARL9-1680432158241_C_Users_28463_AppData_Roaming_Typora_typora-user-images_1680422275044.png]
4.  遍历顺序：在不清楚遍历顺序情况下，最好的方式就是根据状态转移方程画一个简单的递推图，就明白应该怎么初始化
    
    dp\[i\] \[j\] 的推导是 从下到上，从左到右的
5.  返回值：result

#### 代码： ####

/**
        1. 状态定义；布尔类型的 dp[i] [j]表示：在区间 [i, j] 的 子串是否是回文子串，如果是 dp[i] [j] = true，如果不是 dp[i] [j] = false
        2. 状态转移：
        if(s[i] == s[j]) {
    	if(j-i <= 1) { // 指向同一个元素 或 指向的两个元素相邻
    		dp[i][j] = true;
    		result++; // 统计回文子串的数量
    	} else if(dp[i+1][j-1]) {  // 要看 dp[i][j] 是否是回文，就要判断 dp[i+1][j-1] 的情况
    		dp[i][j] = true;
    		result++;
    	}
    } 
        3. 初始化：dp[i] [j] 都要初始化为 false
        4. 遍历顺序： 从下到上，从左到右的
        5. 返回值：result
         */
        public int countSubstrings(String s) {
        
            int n = s.length();
            boolean[][] dp = new boolean[n][n];
            int result = 0;
            for(int i = n-1; i >= 0; i--) {
        
                for(int j = i; j < n; j++) {
        
                    if(s.charAt(i) == s.charAt(j)) {
        
                        if(j - i <= 1) {
        
                            dp[i][j] = true;
                            result++;
                        } else if(dp[i+1][j-1]) {
        
                            dp[i][j] = true;
                            result++;
                        }
                    }
                }
            }
            return result;
        }

## 6. 最长回文子序列 ##

**题目链接：**[516. 最长回文子序列 - 力扣（LeetCode）][516. _ - _LeetCode]

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

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

**示例 1：**

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

**示例 2：**

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

**提示：**

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

#### 思路： ####

在上一题中求的是回文子串的数量，而本题要求的这个回文子序列最长是多少。

并且上一题回文子串要连续，而本道题回文子序列不要去连续。

**下面进行动归五部曲分析**

1.  状态定义：dp\[i\] \[j\] 表示：字符串 s 在 \[i, j\] 范围内最长的回文子序列的长度为 dp\[i\] \[j\]
2.  状态转移：
    
    这里这个可以上一题类似，判断是否是回文，看 s\[i\] 和 s\[j\] 是否是相同的
    
    那么 dp\[i\] \[j\] = dp\[i+1\] \[j-1\] + 2
    
    如果 s\[i\] 和 s\[j\] 不相同，说明 s\[i\] 和 s\[j\] 同时加入，并不能增加 \[i,j\] 区间回文子序列的长度，那么分别加入 s\[i\]、s\[j\] 看看哪个可以组成最长的回文子序列
    
    加入 s\[i\] 的回文子序列长度 dp\[i\] \[j-1\]
    
    加入 s\[j\] 的回文子序列长度 dp\[i+1\] \[j\]
    
    取这两种情况中最大的 dp\[i\] \[j\] = Math.max(dp\[i\] \[j-1\],dp\[i+1\] \[j\])
3.  初始化：![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-f3UzAs8S-1680432158241)(C:\\Users\\28463\\AppData\\Roaming\\Typora\\typora-user-images\\1680425887631.png)\]][img-f3UzAs8S-1680432158241_C_Users_28463_AppData_Roaming_Typora_typora-user-images_1680425887631.png]
    
    当 i 和 j 相同时，递推公式 dp\[i\] \[j\] = dp\[i+1\] \[j-1\] + 2 是计算不到 i 和 j 相同时候的情况，所以需要手动初始化一下 当 i == j 时， dp\[i\] \[j\] = 1，也就是一个字符的回文子序列长度是 1
    
    其他的 dp\[i\] \[j\] 初始为 0 就可以，这样在推导 dp\[i\] \[j\] = Math.max(dp\[i\] \[j-1\],dp\[i+1\] \[j\]) 才不会被初始值覆盖
4.  遍历顺序：从下到上，从左到右
5.  返回值： dp\[0\] \[s.length()\] // 注意这里要返回最长的区间 \[0,s.length()\]

#### 代码： ####

/**
        1. 状态定义；dp[i] [j] 表示：字符串 s 在 [i, j] 范围内最长的回文子序列的长度为 dp[i] [j]
        2. 状态转移：
        if(s.charAt(i) == s.charAt(j)) {
            dp[i][j] = dp[i+1][j-1] + 2;
        } else {
            dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
        }
        3. 初始化：dp[i][i] = 1
        4. 遍历顺序：从下到上，从左到右
        5. 返回值：dp[0][n-1]
        */
        public int longestPalindromeSubseq(String s) {
        
            int n = s.length();
            int[][] dp = new int[n][n];
            // 初始化
            for(int i = 0; i < n; i++) {
        
                dp[i][i] = 1;
            }
            // 遍历
            for(int i = n-1; i >= 0; i--) {
        
                for(int j = i+1; j < n; j++) {
        
                    if(s.charAt(i) == s.charAt(j)) {
        
                        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];
        }

[392. _ - _LeetCode]: https://leetcode.cn/problems/is-subsequence/
[img-VzASfYI1-1680432158238_C_Users_28463_AppData_Roaming_Typora_typora-user-images_1680229780552.png]: https://img-blog.csdnimg.cn/326f5dbe7cba4470b9899ccc48d9ae9d.png
[115. _ - _LeetCode]: https://leetcode.cn/problems/distinct-subsequences/
[img-LKeXYiZE-1680432158239_C_Users_28463_AppData_Roaming_Typora_typora-user-images_1680243888639.png]: https://img-blog.csdnimg.cn/32873048a2ac4fc686c415bea04298c6.png
[583. _ - _LeetCode]: https://leetcode.cn/problems/delete-operation-for-two-strings/
[img-RMrkQVUS-1680432158239_C_Users_28463_AppData_Roaming_Typora_typora-user-images_1680351377996.png]: https://img-blog.csdnimg.cn/bc5b348a19ba46c9a5aa70370ecb592c.png
[72. _ - _LeetCode]: https://leetcode.cn/problems/edit-distance/
[img-dKUqrPVd-1680432158240_C_Users_28463_AppData_Roaming_Typora_typora-user-images_1680351377996.png]: https://img-blog.csdnimg.cn/a7e4ce07c8a440a4a313fcbe73423018.png
[647. _ - _LeetCode]: https://leetcode.cn/problems/palindromic-substrings/
[img-rBKGo1o6-1680432158240_C_Users_28463_AppData_Roaming_Typora_typora-user-images_1680421461589.png]: https://img-blog.csdnimg.cn/d4f6343a0b954507ad9fbc33947e077b.png
[img-TOmMARL9-1680432158241_C_Users_28463_AppData_Roaming_Typora_typora-user-images_1680422275044.png]: https://img-blog.csdnimg.cn/07d7c02a9de74cb6ac7f5e15e954f2ce.png
[516. _ - _LeetCode]: https://leetcode.cn/problems/longest-palindromic-subsequence/
[img-f3UzAs8S-1680432158241_C_Users_28463_AppData_Roaming_Typora_typora-user-images_1680425887631.png]: https://img-blog.csdnimg.cn/653706bf61de44ef8b0aaf0dde36a603.png