力扣算法篇：最长回文子序列（dp）_力扣回文字符串dp解法

动态规划五部曲：
1、确定dp数组及其下标含义
dp[i][j]:字符串在[i,j]范围内的最长的回文子序列的长度为dp[i][j]
2、确定递推式

if s[i] == s[j]  dp[i][j] = dp[i+1][j-1]+2; 不包含i和j相等的情况 所以要单独初始化
if s[i]!=s[j] dp[i][j] = max(dp[i+1][j],dp[i][j-1]);加入s[i]或者s[j]
1
2

3、初始化

 for(int i = 0;i<s.length();i++){
         dp[i][i] = 1;
}
1
2
3

4、遍历顺序
从下到上，从左到右
5、举例推导dp数组

"bbbab"
dp:
1 2 3 3 4 
0 1 2 2 3 
0 0 1 1 3 
0 0 0 1 1 
0 0 0 0 1 
1
2
3
4
5
6
7

题解：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        //回文子序列：跟回文子串相比 回文子序列不是连续的
        //dp[i][j]:字符串在[i,j]范围内的最长的回文子序列的长度为dp[i][j]
        //确定地推公式
        // if s[i] == s[j]  dp[i][j] = dp[i+1][j-1]+2; 不包含i和j相等的情况 所以要单独初始化
        // if s[i]!=s[j] dp[i][j] = max(dp[i+1][j],dp[i][j-1]);加入s[i]或者s[j]
        // 定义dp数组
        vector<vector<int>> dp(s.length(),vector<int>(s.length(),0));
        //初始化
        for(int i = 0;i<s.length();i++){
            dp[i][i] = 1;
        }
        //计算dp数组
        for(int i = s.length()-1;i>=0;i--){
            for(int 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] = max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][s.length()-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27