步骤一、确定状态:
确定dp数组及下标含义
dp[i][j]表示的是字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]
步骤二、推断状态方程:
如果当前的s[i] == s[j], 这说明在中间那个长度的基础上加上这两边的新的字符就OK了,即 最长的回文子序列长度:dp[i][j] = dp[i+1][j-1]+2。
如果当前的s[i] != s[j],这说明i-j之间的最长回文子序列有两种方式转换来了,第一个就是把i 位置的字符拼到中间那块,求最长回文子序列dp[i][j-1], 第二个就是把j位置的字符拼到中间 那块,求最长回文子序列dp[i+1][j],那么取最长即可。dp[i][j] = max(dp[i][j-1], dp[i+1][j])
步骤三、规定初始条件:
初始条件:
全局初始化为0,对角线初始化为1。
步骤四、计算顺序:
遍历i的时候一定要从下到 上遍历,这样才能保证,下 一行的数据是经过计算的。 即逆向遍历行,正向遍历列。
class Solution:def longestPalindromeSubseq(self, s: str) -> int:if len(s) == 1:return 1dp = [[0 for _ in range(len(s))] for _ in range(len(s))]for i in range(len(s)):dp[i][i] = 1for i in range(len(s)-1, -1, -1):for j in range(i+1, len(s)):if s[i] == s[j]:dp[i][j] = dp[i+1][j-1] + 2else:dp[i][j] = max(dp[i+1][j], dp[i][j-1])return dp[0][-1]
如果觉得《120. Leetcode 516. 最长回文子序列 (动态规划-子序列问题)》对你有帮助,请点赞、收藏,并留下你的观点哦!