动态规划

字符串

  • 最长回文子序列

    难度：中等

    给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
    示例 1：
    输入：s = “bbbab”
    输出：4
    解释：一个可能的最长回文子序列为 “bbbb”

    示例 2：
    输入：s = “cbbd”
    输出：2
    解释：一个可能的最长回文子序列为 “bb” 。

  • 方法一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution:
      def longestPalindromeSubseq(self, s: str) -> int:
          n = len(s)
          dp = [[0] * n for _ in range(n)]
          for i in range(n-1,-1,-1):
              dp[i][i] = 1
              for j in range(i+1,n):
                  if s[i]==s[j]:
                      dp[i][j] = dp[i+1][j-1]+2
                  else:
                      dp[i][j]=max(dp[i+1][j],dp[i][j-1])
          return dp[0][-1]

    解析

    复杂度分析
    时间复杂度：O(n^2)，其中 n 是字符串 s 的长度。动态规划需要计算的状态数是 O(n^2)。
    空间复杂度：O(n^2)，其中 n 是字符串 s 的长度。需要创建二维数组 dp，空间是 O(n^2)。