516.longest-palindromic-subsequence.md

516. 最长回文子序列

<思路 1>线性动态规划

最优子状态：dp[i][j]表示s[i, j]的区间中最长回文子序列的长度

状态转移：

如果s[i] == s[j]，则dp[i][j] = dp[i+1][j-1] + 2 否则，dp[i][j] = max(dp[i+1][j], dp[i][j-1])

边界:

当 len=1 时，dp[i][i] = 1 当 len=2 时，dp[i][i+1] = s[i] == s[i+1] ? 2:1

len>=3 时，满足上述状态转移方程

代码实现

java

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int dp[][] = new int[n][n];

        for (int i=0; i< n; i++)dp[i][i] = 1;
        for (int i = 0; i<n-1; i++)dp[i][i+1] = s.charAt(i) == s.charAt(i+1) ? 2: 1;
        for (int len = 3; len<=n; len++){
            for (int i = 0; i+len-1 < n; i++){
                int j = i+len -1 ;
                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][n-1];
    }
}

cpp

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

拓展：

如何打印出最长回文子序列？

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));

        vector<vector<int>> pi(s.size(), vector<int>(s.size(), 0));
        // len = 1
        for (int i = 0; i < s.size(); i++) {
            dp[i][i] = 1;
        }
        // len = 2
        for (int i = 0; i < s.size() - 1; i++) {
            dp[i][i + 1] = s[i] == s[i + 1] ? 2 : 1;
        }
        // len >= 3
        for (int len = 3; len <= s.size(); len++) {
            for (int i = 0; i + len <= s.size(); i++) {
                int j = i + len - 1;
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                    pi[i][j] = 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                    if (dp[i][j] == dp[i + 1][j]) pi[i][j] = 0;
                    else pi[i][j] = 1;
                }
            }
        }

        char *res = new char[dp[0][s.size() - 1]];
        int p = 0, q = dp[0][s.size() - 1] - 1;
        int i = 0, j = s.size() - 1;
        while (i <= j) {
            if (i == j) {
                res[p] = s[i];
                break;
            }
            if (i + 1 == j) {
                res[p] = s[i];
                res[q] = s[j];
                break;
            }
            if (pi[i][j] == 0) {
                i++;
            } else if (pi[i][j] == 1) {
                j--;
            } else {
                res[p++] = s[i++];
                res[q--] = s[j--];
            }
        }
        cout << "longestPalindromeSubseq is:" << res << endl;
        return dp[0][s.size() - 1];
    }
};

javascript

var longestPalindromeSubseq = function (s) {
  let dp = new Array(s.length);
  for (let i = 0; i < dp.length; i++) {
    dp[i] = new Array(s.length).fill(0);
  }

  for (let i = s.length - 1; i >= 0; i--) {
    dp[i][i] = 1;
    for (let j = i + 1; j < s.length; j++) {
      if (s[i] == s[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][s.length - 1];
};

<思路 2>通过最长子序列求解

s 的最长回文子序列，其实就是求 s 和 s 的逆序的最长公共子序列

var longestPalindromeSubseq = function (s) {
  let s1 = s.split("").reverse().join("");
  return longestCommonSubsequence(s, s1);
};

var longestCommonSubsequence = function (text1, text2) {
  let dp = new Array(text1.length + 1);
  for (let i = 0; i < dp.length; i++) {
    dp[i] = new Array(text2.length + 1).fill(0);
  }
  for (let i = 1; i < dp.length; i++) {
    for (let j = 1; j < dp[0].length; j++) {
      if (text1[i - 1] == text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[text1.length][text2.length];
};