牛客对应题目链接：最长回文子序列_牛客题霸_牛客网 (nowcoder.com)
一、分析题目
基础的区间 dp 问题：
1、状态表示
dp[i][j] 表示：字符串 [i, j] 区间内的最长回文子序列的长度。
2、状态转移方程
- 当 i > j，dp[i][j] = 0（不讨论这种情况，可以保证不存在这种情况）
- 当 i == j 的时候，只有⼀个字符，长度为 1，即 dp[i][j] = 1；
- 当 i < j 的时候，分情况讨论：
- s[i] == s[j]：dp[i][j] = dp[i+1][j-1] + 2;
- s[i] != s[j]：dp[i][j] = max(dp[i+1][j], dp[i][j-1])；
3、初始化
根据状态转移方程，可以知道 dp[i][j] 的取值方向只会从它的左边、左下、下面三个方向去取，而这些方向除了 i==j 时是初始化为 1 的以外，其它的都是 i > j，不需要另外进行初始化。
4、填表顺序
从下往上，从左往右。
5、返回值
dp[0][n-1]（可以返回状态表示的含义去思考返回值）
二、代码
1、力扣AC代码
//动态规划-二维dp class Solution { public: int longestPalindromeSubseq(string s) { int n=s.size(); vector<vector<int>> dp(n, vector<int>(n)); for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(i==j) dp[i][j]=1; for(int i=n-1; i>=0; i--) { for(int j=i+1; j<n; j++) { if(s[i]==s[j]) 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]; } }; //动态规划-二维dp-优化 class Solution { public: int longestPalindromeSubseq(string s) { int n=s.size(); vector<vector<int>> dp(n, vector<int>(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[i]==s[j]) 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]; } };
2、值得学习的代码
#include <iostream> #include <string> using namespace std; int dp[1010][1010]; int main() { string s; cin >> s; int n = s.size(); for(int i = n - 1; i >= 0; i--) { dp[i][i] = 1; for(int j = i + 1; j < n; j++) { if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2; else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); } } cout << dp[0][n - 1] << endl; return 0; }
三、反思与改进
做这道题时，我还是想到了之前写过的5. 最长回文子串 - 力扣（LeetCode），然后就还是按着之前的分类讨论的思路去写了，结果只能通过一般的测试样例。忽略了这两道题目的不同之处：之前写的题目要求的是子串，说明是连续序列；而这道题目要求的是子序列，并没有要求是连续的，所以这两道题目的解法肯定不一样。
本题应该是与516. 最长回文子序列 - 力扣（LeetCode）要求一致，不过这道题之前也写过，印象不深刻，说明没有掌握这类题目的本质，不熟练就多做几次吧。
