LeetCode516：最长回文子序列

题目链接：516. 最长回文子序列 - 力扣（LeetCode）

代码如下：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size() + 1, vector<int>(s.size() + 1, 0));
        for(int i = 0; i < s.size(); i++)   dp[i][i] = 1;
        for(int i = s.size() - 1; i >= 0; i--)
        {
            for(int j = i + 1; j < s.size(); 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][s.size() - 1];
    }
};

dp的含义：[i, j]最长回文子序列长度

dp的递推公式：

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]);
}

这个递推公式就是先看s[i] == s[j]，如果相等的话，那么就dp[i][j] = dp[i + 1][j - 1] + 2，这个也就是把头部和尾部相等的也算上了，如果不相等话，那么再分成两个情况，第一个是让头部的元素往后走，但是尾部的元素不走，也就是dp[i + 1][j]，第二种情况就是让尾部往前走，头部元素不走也就是dp[i][j - 1],这两个求一个最大值。

初始化：这个时候我们需要考虑，要是i==j的情况的话怎么办，那么这个时候就需要dp[i][i] = 1即可，要不然有些方向我们推到不出来

遍历顺序：这个时候我们就要画出来一个2*2的表格，通过递推公式这个时候看见这个dp[i - 1][j - 1]是通过由下到上，由左到右推导出来的，那么这个时候我们就需要从后往前遍历了。

返回值：这个返回的就是头部元素的位置和这个字符串末尾元素的位置。

原文地址：https://blog.csdn.net/Ricky_youngone/article/details/143355679

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！