516 Longest Palindromic Subsequence 最长回文子序列

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

详见：https://leetcode.com/problems/longest-palindromic-subsequence/description/

C++：

class Solution {

public:

    int longestPalindromeSubseq(string s)

    {

        int n = s.size();

        vector<vector<int>> dp(n, vector<int>(n));

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

                }

            }

        }

        return dp[0][n - 1];

    }

};

参考：http://www.cnblogs.com/grandyang/p/6493182.html

巴特西

516 Longest Palindromic Subsequence 最长回文子序列

最新文章

热门文章