leetcode-516-区间DP-最长回文子序列

发表于 | 分类于

题目

1.png

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 动态规划
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();

        // 在子串s[i...j]中，最长回文子序列的长度是dp[i][j]
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for(int i = 0; i < n; ++i) dp[i][i] = 1;

        for(int i = n - 2; 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];
    }
};