Code & Func

第27天。

一道动态规划的问题，我们假定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
int longestPalindromeSubseq1(string s) {
2
    int size = s.size();
3
    vector<vector<int>> dp(size, vector<int>(size, 0));
4
    for(int i = size - 1;i >= 0; i--) {
5
        dp[i][i] = 1;
6
        for(int j = i + 1;j < size;j++) {
7
            if (s[i] == s[j]) {
8
                dp[i][j] = dp[i+1][j-1] + 2;
9
            } else {
10
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
11
            }
12
        }
13
    }
14
    return dp[0][size-1];
15
}

为了减少空间复杂度，我们可以这样优化：

1
int longestPalindromeSubseq(string s) {
2
    int size = s.size();
3

4
    vector<int> dp1(size, 0), dp2(size, 0);
5
    for(int i = size - 1;i >= 0; i--) {
6
        dp2[i] = 1;
7
        dp1[i] = 0;
8
        for(int j = i + 1;j < size;j++) {
9
            if (s[i] == s[j]) {
10
                // dp[i][j] = dp[i+1][j-1] + 2;
11
                dp2[j] = dp1[j-1] + 2;
12
            } else {
13
                // dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
14
                dp2[j] = max(dp1[j], dp2[j-1]);
15
            }
6 collapsed lines
16
        }
17

18
        swap(dp1, dp2);
19
    }
20
    return dp1[size-1];
21
}