题目地址：https://leetcode.com/problems/longest-palindromic-subsequence/description/

题目描述

Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.

Example 1:

Input:

"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".

Example 2:

Input:

"cbbd"
Output:
2
One possible longest palindromic subsequence is "bb".

题目大意

找出一个字符串中最长的回文序列的长度。注意序列可以是不连续的，而子字符串是连续的。

解题思路

做完昨天的每日一题 446. 等差数列划分 II - 子序列open in new window 之后，相信大家对于子序列问题的套路已经更加了解了。子序列问题不能用滑动窗口了，可以用动态规划来解决。子序列问题的经典题目就是 300. 最长递增子序列open in new window，务必掌握。

先从整体思路说起。

子序列问题，由于是数组中的非连续的一个序列，使用动态规划求解时，避免不了二重循环：第一重循环是求解动态规划的每一个状态 dp[i],(0<=i<=N) ，第二重循环是向前寻找上一个子序列的结尾 j,(0<=j<i)$ 来和 i 一起构成满足题意的新的子序列。

• 对于「最长递增子序列」问题，我们对 i,j 的要求是 nums[i]>nums[j]，即递增；
• 对于「能构成等差数列的子序列」问题，我们对 i,j 的要求是 num[i] 可以在 nums[j] 的基础上构成等差数列。
• 对于「最长回文子序列」问题，我们对 i,j 本身的取值没有要求，但是希望能够成最长的回文子串。

在动态规划问题中，我们找到一个符合条件的 j ，然后就可以通过状态转移方程由 dp[j] 推导出 dp[i] 。

然后，我理一下本题的解法。

当已知一个序列是回文时，在其首尾添加元素后的序列存在两种情况：

1、 首尾元素相等，则最长回文的长度+2；
2、 首尾元素不相等，则最长回文序列长度为仅添加首元素时的最长回文长度与仅添加尾元素时的最长回文长度的最大值；

状态定义： dp[i][j] 表示 s[i…j] 中的最长回文序列长度。

状态转移方程：

1、 i>j，dp[i][j]=0；
2、 i==j，dp[i][j]=1；
3、 i<j且s[i]==s[j]，dp[i][j]=dp[i+1][j−1]+2；
4、 i<j且s[i]！=s[j]，dp[i][j]=max(dp[i+1][j]，dp[i][j−1])；

遍历顺序： 从状态转移方程可以看出，计算 dp[i][j] 时需要用到 dp[i+1][j−1] 和 dp[i+1][j]，所以对于 i 的遍历应该从后向前；对于 j 的遍历应该从前向后。

返回结果： 最后返回 dp[0][s.length()−1]。

代码

提供了三种语言的代码。

java 代码

class Solution {
    public int longestPalindromeSubseq(String s) {
        int size = s.length();
        int[][] dp = new int[size][size];
        for(int i = size - 1; i >= 0; i--){
            dp[i][i] = 1;
            for(int j = i + 1; j < size; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }else{
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][size - 1];
    }
}

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

C++代码：

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

python 代码：

class Solution:
    def longestPalindromeSubseq(self, s):
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            dp[i][i] = 1
            for j in range(i + 1, n):
                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]

1 2 3 4 5 6 7 8 9 10 11 12

• 时间复杂度：O(N2)
• 空间复杂度：O(N2)

刷题心得

子序列的动态规划解法：两重循环。其实就看对于每个 i，当找到满足题目要求的 j 的时候，状态转移方程怎么变化。

参考：http://blog.csdn.net/camellhf/article/details/70337501

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发