Posted on 2023-04-14 18:03
Uriel 閱讀(41)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
求字符串的最長回文子序列，O(n^2) DP
1 #516
2 #Runtime: 953 ms (Beats 76.88%)
3 #Memory: 28.6 MB (Beats 58.38%)
4
5 class Solution(object):
6 def longestPalindromeSubseq(self, s):
7 """
8 :type s: str
9 :rtype: int
10 """
11 n = len(s)
12 dp = [[0] * n for _ in range(n)]
13 for i in range(n - 1, -1, -1):
14 dp[i][i] = 1
15 for j in range(i + 1, n):
16 if s[i] == s[j]:
17 dp[i][j] = dp[i + 1][j - 1] + 2
18 else:
19 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
20 return dp[0][n-1]