Leetcode|线性序列|516. 最长回文子序列

1 动态规划

【dp数组含义】：s[i, j]的子序列最长为dp[i][j] 【状态转移方程】：

• 两字符相等——则回文子序列长度自增2

代码语言：javascript复制

dp[i][j] = dp[i   1][j - 1]   2;

• 两字符不等——比较添加s[i]或s[j]可以增长子序列

代码语言：javascript复制

dp[i][j] = max(dp[i][j - 1], dp[i   1][j]);

完整代码如下

代码语言：javascript复制

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int size = s.size();
        // dp数组含义：s[i, j]的子序列最长为dp[i][j]
        vector<vector<int>> dp(size, vector<int>(size, 0));
        for (int i = size - 1; i >= 0; i--){
            // 边界初始化(对角线全为1))
            dp[i][i] = 1;
            for (int j = i   1; j < size; j  ) {
                // 1.两字符相等——则回文子序列长度自增2
                if (s[i] == s[j])
                    dp[i][j] = dp[i   1][j - 1]   2;
                // 2.两字符不等——比较添加s[i]或s[j]可以增长子序列
                else 
                    dp[i][j] = max(dp[i][j - 1], dp[i   1][j]);
            }
        }
        return dp[0][size - 1];
    }
};

致谢

图片来源于「代码随想录」公众号，欢迎大家关注这位大佬的公号

dp 动态规划 公众号 数组

0 人点赞