步驟一、確定狀態(tài):

確定dp數(shù)組及下標(biāo)含義
dp[i][j]表示的是字符串s在[i, j]范圍內(nèi)最長的回文子序列的長度為dp[i][j]

步驟二、推斷狀態(tài)方程:

如果當(dāng)前的s[i] == s[j]， 這說明在中間那個長度的基礎(chǔ)上加上這兩邊的新的字符就OK了，即 最長的回文子序列長度:dp[i][j] = dp[i+1][j-1]+2。

如果當(dāng)前的s[i] != s[j]，這說明i-j之間的最長回文子序列有兩種方式轉(zhuǎn)換來了，第一個就是把i 位置的字符拼到中間那塊，求最長回文子序列dp[i][j-1]， 第二個就是把j位置的字符拼到中間 那塊，求最長回文子序列dp[i+1][j]，那么取最長即可。dp[i][j] = max(dp[i][j-1], dp[i+1][j])

步驟三、規(guī)定初始條件:

初始條件:

全局初始化為0，對角線初始化為1。

步驟四、計算順序:

遍歷i的時候一定要從下到 上遍歷，這樣才能保證，下 一行的數(shù)據(jù)是經(jīng)過計算的。 即逆向遍歷行，正向遍歷列。

?

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]

?

總結(jié)

以上是生活随笔為你收集整理的120. Leetcode 516. 最长回文子序列 (动态规划-子序列问题)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。