**Idea:**

dp[i][j] = longest palindrome subsequence of s[i to j].

If s[i] == s[j], dp[i][j] = 2 + dp[i+1][j - 1]

Else, dp[i][j] = max(dp[i+1][j], dp[i][j-1])

**Rolling array O(2n) space**

```
class Solution(object):
def longestPalindromeSubseq(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
dp = [[1] * 2 for _ in range(n)]
for j in xrange(1, len(s)):
for i in reversed(xrange(0, j)):
if s[i] == s[j]:
dp[i][j%2] = 2 + dp[i + 1][(j - 1)%2] if i + 1 <= j - 1 else 2
else:
dp[i][j%2] = max(dp[i + 1][j%2], dp[i][(j - 1)%2])
return dp[0][(n-1)%2]
```

**Further improve space to O(n)**

```
class Solution(object):
def longestPalindromeSubseq(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
dp = [1] * n
for j in xrange(1, len(s)):
pre = dp[j]
for i in reversed(xrange(0, j)):
tmp = dp[i]
if s[i] == s[j]:
dp[i] = 2 + pre if i + 1 <= j - 1 else 2
else:
dp[i] = max(dp[i + 1], dp[i])
pre = tmp
return dp[0]
```