动态规划运用二维dp数组
1、确定状态：
（1）最后一步----字符串s[i:j]中的最长回文子序列
（2）子问题
2、转移方程
（1）s[i]==s[j]
把字符串左右同时缩小一下+2，上图情况1 +2
（2）s[i]!=s[j]
不相等的话说明这两个字符不可能同时出现在s[i:j]的最长回文子序列
选择上图情况2和3较大的一个
3、初始状态
dp[i][i] = 1
4、计算顺序
从左到右 知道j，要先知道 j-1
从下到上 知道i，要先知道 i+1
class Solution: def longestPalindromeSubseq(self, s: str) -> int: n = len(s) dp=[[0]*n for i 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][n-1]
72、编辑距离
原文：https://www.cnblogs.com/zhaojiayu/p/14532590.html