動機

我忘了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)