Longest Palindromic Subsequence

LeetCode

第27天。

今天的题目是Longest Palindromic Subsequence：

一道动态规划的问题，我们假定dp[i, j]是字符串S[i:j]最长回文串的长度。那么我们可以写出如下动规方程：

$$
dp[i, j] = \left{
\begin{aligned}
dp[i-1, j-1] + 2 & &,s[i] = s[j] \
max{d[i-1,j], dp[i, j-1]} & &,s[i] \neq s[j]
\end{aligned}
\right.
$$

有了动规方程后，这个问题就简单多了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int longestPalindromeSubseq1(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
19
20
21
int longestPalindromeSubseq(string s) {
    int size = s.size();
    
    vector<int> dp1(size, 0), dp2(size, 0);
    for(int i = size - 1;i >= 0; i--) {
        dp2[i] = 1;
        dp1[i] = 0;
        for(int j = i + 1;j < size;j++) {
            if (s[i] == s[j]) {
                // dp[i][j] = dp[i+1][j-1] + 2;
                dp2[j] = dp1[j-1] + 2;
            } else {
                // dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
                dp2[j] = max(dp1[j], dp2[j-1]);
            }
        }
        
        swap(dp1, dp2);
    }
    return dp1[size-1];
}