516.最长回文子序列

刷算法题：

第一遍：1.看5分钟，没思路看题解

2.通过题解改进自己的解法，并且要写每行的注释以及自己的思路。

3.思考自己做到了题解的哪一步，下次怎么才能做对(总结方法)

4.整理到自己的自媒体平台。

5.再刷重复的类似的题目，根据时间和任务安排刷哪几个板块

6.用c++语言 都刷过一遍了 就刷中等

一.题目

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

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

示例 1：

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

示例 2：

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

提示：

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

二、反思

1.自己的解法

无

2.题目的解法 

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.length();
        vector<vector<int>> dp(n,vector<int>(n));
        //dp【i】【j】是i到j的最长子序列。
        for(int i=n-1;i>=0;i--){
            dp[i][i]=1;
            int c1=s[i];
            for(int j=i+1;j<n;j++){//只要是子序列这么做不断向后遍历，就等于删除了。
                int c2=s[j];
                if(c1==c2){
                    dp[i][j]=dp[i+1][j-1]+2;
                }else {
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
                }
                
            }

        }
        return dp[0][n-1];
    }
};

 3.思路的异同

对于一个子序列而言，如果它是回文子序列，并且长度大于 2，那么将它首尾的两个字符去除之后，它仍然是个回文子序列。因此可以用动态规划的方法计算给定字符串的最长回文子序列。

用 dp[i][j] 表示字符串 s 的下标范围 [i,j] 内的最长回文子序列的长度。假设字符串 s 的长度为 n，则只有当 0≤i≤j<n 时，才会有 dp[i][j]>0，否则 dp[i][j]=0。（这里就强调了for遍历顺序）

由于任何长度为 1 的子序列都是回文子序列，因此动态规划的边界情况是，对任意 0≤i<n，都有 dp[i][i]=1。

当 i<j 时，计算 dp[i][j] 需要分别考虑 s[i] 和 s[j] 相等和不相等的情况：

如果 s[i]=s[j]，则首先得到 s 的下标范围 [i+1,j−1] 内的最长回文子序列，然后在该子序列的首尾分别添加 s[i] 和 s[j]，即可得到 s 的下标范围 [i,j] 内的最长回文子序列，因此 dp[i][j]=dp[i+1][j−1]+2；

如果 s[i]=s[j]，则 s[i] 和 s[j] 不可能同时作为同一个回文子序列的首尾，因此 dp[i][j]=max(dp[i+1][j],dp[i][j−1])。

由于状态转移方程都是从长度较短的子序列向长度较长的子序列转移，因此需要注意动态规划的循环顺序。

最终得到 dp[0][n−1] 即为字符串 s 的最长回文子序列的长度。

三.进步的地方

 上一段直接封神