I got TLE with standard dp. The work around is to check the whether the given string itself is a palindrome and use O(N) space.

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