動機
我忘了dp
Problem
Given a string s
, find the longest palindromic subsequence's length in s
.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: s = "bbbab"Output: 4Explanation: One possible longest palindromic subsequence is "bbbb".
Example 2:
Input: s = "cbbd"Output: 2Explanation: One possible longest palindromic subsequence is "bb".
Constraints:
1 <= s.length <= 1000
s
consists only of lowercase English letters.
Sol
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
@cache
def dp(i,j):
if i > j:
return 0
elif i == j:
return 1
elif s[i] == s[j]:
return 2+dp(i+1,j-1)
else:
return max(dp(i+1,j),dp(i,j-1))
return dp(0,len(s)-1)