516. 最长回文子序列

如果暂时想不到状态转移方程，可以先确定base case和最终状态，然后通过它们的相对位置，来猜测状态转移方程，猜测dp[i][j]可能从哪些状态转移而来。以本题为例：

base case：dp表的左下角三角形为0，对角线元素为1（回文子序列为自己）

最终状态是dp[o][n-1]

对于dp[i][j],它知道了左边元素，下边元素，左下边元素; 此外，通过结合最终状态的位置，所以考虑从左到右从下到上的次序遍历dp表。于是思考状态转移方程及遍历过程：
        for i in range(n-2,-1,-1):
            for j in range(i+1,n):
                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])

dp数组的含义：s[i…j] 中最长回文子序列的长度保存在dp[i][j] 中
状态转移方程：如果i处和j处的字符相同，则从短串s[i+1…j-1]中扩充2（dp[i][j]=dp[i+1][j-1]+2）。否则继承 s[i+1…j] ， s[i…j-1] 的最长回文子序列长度的最大值（max(dp[i+1][j],dp[i][j-1])）
base case: dp 数组先初始化为 0 （而且对角线下半部分的三角形表示i > j, 不可能出现这种情况，因此为0）。i 和 j 指向同一个字符时，回文子序列为其本身，因此对角线处的dp数组元素初始化为1

class Solution(object):
    def longestPalindromeSubseq(self, s):
        n=len(s)
        dp=[[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i]=1

        for i in range(n-2,-1,-1):
            for j in range(i+1,n):
                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][-1]