LeetCode-516. 最长回文子序列

我就是我 2024-03-24 13:00 67阅读 0赞

#### 动态规划 ####

*   *  本题思路
     *  动态规划

题目来源  
[516. 最长回文子序列][516.]

### 本题思路 ###

回文子串是要连续的，回文子序列可不是连续的！ 回文子串，回文子序列都是动态规划经典题目。和[LeetCode-647. 回文子串][LeetCode-647.]很像

### 动态规划 ###

*  1.确定dp数组（dp table）以及下标的含义

dp\[i\]\[j\]：字符串s在\[i, j\]范围内最长的回文子序列的长度为dp\[i\]\[j\]。

*  2.确定递推公式

在判断回文子串的题目中，关键逻辑就是看s\[i\]与s\[j\]是否相同。  
如果s\[i\]与s\[j\]相同，那么dp\[i\]\[j\] = dp\[i + 1\]\[j - 1\] + 2;  
![在这里插入图片描述][68bd94e4048748bbab03a3a65b2e57cf.png]  
如果s\[i\]与s\[j\]不相同，说明s\[i\]和s\[j\]的同时加入 并不能增加\[i,j\]区间回文子序列的长度，那么分别加入s\[i\]、s\[j\]看看哪一个可以组成最长的回文子序列。  
加入s\[j\]的回文子序列长度为dp\[i + 1\]\[j\]。  
加入s\[i\]的回文子序列长度为dp\[i\]\[j - 1\]。  
那么dp\[i\]\[j\]一定是取最大的，即：dp\[i\]\[j\] = max(dp\[i + 1\]\[j\], dp\[i\]\[j - 1\]);  
![在这里插入图片描述][c951ad2a71b2472dab202380ff00b33b.png]

*  3.dp数组如何初始化

首先要考虑当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\] = max(dp\[i + 1\]\[j\], dp\[i\]\[j - 1\]); 中dp\[i\]\[j\]才不会被初始值覆盖。

for (int i = 0; i < s.size(); i++) dp[i][i] = 1;

*  4.确定遍历顺序  
    从递归公式中，可以看出，dp\[i\]\[j\] 依赖于 dp\[i + 1\]\[j - 1\] ，dp\[i + 1\]\[j\] 和 dp\[i\]\[j - 1\]，如图：

![在这里插入图片描述][ded75a0792de43aa9233b9e591363c49.png]  
所以遍历i的时候一定要从下到上遍历，这样才能保证下一行的数据是经过计算的。  
j的话，可以正常从左向右遍历。

*  5.举例推导dp数组

输入s:“cbbd” 为例，dp数组状态如图：

![在这里插入图片描述][6c0959b45b9649808fe053b6c0936b56.png]  
代码实现

class Solution {
        
        public int longestPalindromeSubseq(String s) {
        
            int[][] dp = new int[s.length()][s.length()];
            for(int i = s.length()-1;i>=0;i--){
        
                dp[i][i] = 1; // 初始化
                for(int j = i+1;j<s.length();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][s.length()-1];
        }
    }

![在这里插入图片描述][ea43015d57f247dea1db581c2974c62f.png]

[516.]: https://leetcode.cn/problems/longest-palindromic-subsequence/
[LeetCode-647.]: https://donglin.blog.csdn.net/article/details/129897413
[68bd94e4048748bbab03a3a65b2e57cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/c5b933f9c7f54f7fbd14d43ec55ab21a.png
[c951ad2a71b2472dab202380ff00b33b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/94d06d17407f4ec995279ccc47595770.png
[ded75a0792de43aa9233b9e591363c49.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/c41141c467c24250a117aaf8dc81a9b4.png
[6c0959b45b9649808fe053b6c0936b56.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/cb54693f8911438c82ad58faa72a377b.png
[ea43015d57f247dea1db581c2974c62f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/ae2a874914e045f69d967229fd59dc48.png