text: # Time:  O(n^2)
  # Space: O(n)
  
  # Given a string s, find the longest palindromic subsequence's length in s.
  # You may assume that the maximum length of s is 1000.
  #
  # Example 1:
  # Input:
  #
  # "bbbab"
  # Output:
  # 4
  # One possible longest palindromic subsequence is "bbbb".
  # Example 2:
  # Input:
  #
  # "cbbd"
  # Output:
  # 2
  
  class Solution(object):
      def longestPalindromeSubseq(self, s):
          """
          :type s: str
          :rtype: int
          """
          if s == s[::-1]:
              return len(s)
  
          dp = [[1] * len(s) for _ in xrange(2)]
          for i in reversed(xrange(len(s))):
              for j in xrange(i+1, len(s)):
                  if s[i] == s[j]:
                      dp[i%2][j] = 2 + dp[(i+1)%2][j-1] if i+1 <= j-1 else 2
                  else:
                      dp[i%2][j] = max(dp[(i+1)%2][j], dp[i%2][j-1])
          return dp[0][-1]
  