class Solution {
public:
int longestPalindromeSubseq(string s) {
int size = s.size();
if (size <= 1) {
return size;
}
/*dp[i][j] means from index i to index j, the longest palindromic subsequence*/
vector<vector<int> > dp(size + 1, vector<int> (size + 1, 0));
/*dp initialization dp[i][i] means contains one character so it equals one*/
for (int i = 1; i <= size; ++i) {
dp[i][i] = 1;
}
/*j means move the right i means mean to left*/
for (int j = 1; j < size; ++j) {
for (int i = j  1; i >= 0; i) {
if (s[i] == s[j]) {
/*bab i = 0, j = 2 dp[0][2] = dp[1][1] + 2, and like lcs we should compare to
dp[0][1] and d[1][2] to get the longest*/
dp[i][j] = max(dp[i+1][j  1] + 2, max(dp[i+1][j], dp[i][j1]));
}
else {
dp[i][j] = max(dp[i+1][j1],max(dp[i+1][j], dp[i][j1]));
}
}
}
return dp[0][size  1];
}
};
very easy to understand with detailed explain using dynamic programming just like longest common subsequence


@540485909 Why my python version TLE?
class Solution(object): def longestPalindromeSubseq(self, s): """ :type s: str :rtype: int """ N = len(s) dp = [[0 for _ in range(N)] for __ in range(N)] for i in range(N): dp[i][i] = 1 for j in range(1, N): for i in range(j1, 1, 1): if s[i]==s[j]: dp[i][j] = max([ dp[i+1][j1]+2, dp[i+1][j], dp[i][j1] ]) else: dp[i][j] = max([ dp[i+1][j1], dp[i+1][j], dp[i][j1] ]) return dp[0][N1]

@Chengcheng.Pei thanks for your comment, I think this may be the reason the python is slow than c++, so you can't AC using an algorithm of O(n2), here is an example of python AC code python ac code