力扣 516. 最长回文子序列 dp_力扣516

https://leetcode-cn.com/problems/longest-palindromic-subsequence/

思路一：$d{p}_{i,j}$表示区间$[i,j]$的最长回文子序列的长度，显然$d{p}_{i,i}=1$，对于区间$[i,j]$如果有$s_i=s_j$，那么有$d{p}_{i,j}=d{p}_{i+1,j-1}+2$；否则$d{p}_{i,j}=max(d{p}_{i+1,j},d{p}_{i,j-1})$。为什么第一种情况可以直接赋值，不用判断取最大值呢？因为它不可能比后两种情况更差。

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 j=i-1;j>=0;j--)
            {
                if(s[i]==s[j])
                    dp[j][i]=dp[j+1][i-1]+2;
                else
                    dp[j][i]=max(dp[j][i-1],dp[j+1][i]);
            }
        }
        return dp[0][n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

思路二：转换一下思路，最长回文子序列就等于该序列与其逆序列的最长公共子序列，经典LCS问题。