qidao123.com技术社区-IT企服评测·应用市场

标题: 【LeetCode 刷题】动态规划(5)-子序列题目 [打印本页]
作者: 铁佛    时间: 2025-3-30 08:43
标题: 【LeetCode 刷题】动态规划(5)-子序列题目
此博客为《代码随想录》动态规划章节的学习条记，主要内容为动态规划子序列题目的相干题目剖析。

   
  不连续子序列

300. 最长递增子序列

题目链接
  1. class Solution:
  2.     def lengthOfLIS(self, nums: List[int]) -> int:
  3.         n = len(nums)
  4.         dp = [1 for _ in range(n)]
  5.         res = 1
  6.         for i in range(1, n):
  7.             for j in range(i):
  8.                 if nums[j] < nums[i]:
  9.                     dp[i] = max(dp[i], dp[j] + 1)
  10.             res = max(res, dp[i])
  11.         return res
复制代码

1143. 最长公共子序列

题目链接
  1. class Solution:
  2.     def longestCommonSubsequence(self, text1: str, text2: str) -> int:
  3.         m, n = len(text1), len(text2)
  4.         dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
  5.         for i in range(1, m + 1):
  6.             for j in range(1, n + 1):
  7.                 if text1[i-1] == text2[j-1]:
  8.                     dp[i][j] = dp[i-1][j-1] + 1
  9.                 else:
  10.                     dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  11.         return dp[m][n]
复制代码


  • 状态定义：dp[j] 表现考虑 text1 前 i 个字符、text2 前 j 个字符的最长公共子序列长度（不要求肯定以 text1[i-1] 和 text2[j-1] 末端）
  • 递推公式：

    • 当前字符雷同时，dp[j] = dp[i-1][j-1] + 1（不考虑 dp[i-1][j] 和 dp[j-1]，肯定小于即是 dp[i-1][j-1] + 1）
    • 当前字符差别时，dp[j] = max(dp[i-1][j], dp[j-1])

1035. 不相交的线

题目链接
  1. class Solution:
  2.     def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
  3.         m, n = len(nums1), len(nums2)
  4.         dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
  5.         for i in range(1, m + 1):
  6.             for j in range(1, n + 1):
  7.                 if nums1[i-1] == nums2[j-1]:
  8.                     dp[i][j] = dp[i-1][j-1] + 1
  9.                 else:
  10.                     dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  11.         return dp[m][n]
复制代码


  • 与上题完全雷同
连续子序列

674. 最长连续递增序列

题目链接
  1. class Solution:
  2.     def findLengthOfLCIS(self, nums: List[int]) -> int:
  3.         n = len(nums)
  4.         dp = [1 for _ in range(n)]
  5.         res = 1
  6.         for i in range(1, n):
  7.             if nums[i] > nums[i-1]:
  8.                 dp[i] = dp[i-1] + 1
  9.             res = max(res, dp[i])
  10.         return res
复制代码


  • 与 “300. 最长递增子序列” 相比，此题要求子序列连续
  • 递推公式：仅用考虑前一个元素

    • 满足递增关系，dp = dp[i-1] + 1
    • 不满足递增关系，dp = 1

718. 最长重复子数组

题目链接
  1. class Solution:
  2.     def findLength(self, nums1: List[int], nums2: List[int]) -> int:
  3.         m, n = len(nums1), len(nums2)
  4.         dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
  5.         res = 0
  6.         for i in range(1, m + 1):
  7.             for j in range(1, n + 1):
  8.                 if nums1[i-1] == nums2[j-1]:
  9.                     dp[i][j] = dp[i-1][j-1] + 1
  10.                 res = max(res, dp[i][j])
  11.         return res
复制代码


  • 与 “1143. 最长公共子序列” 相比，此题要求子序列连续
  • 状态定义：dp[j] 表现以 nums1[i-1] 和 nums2[j-1] 末端的数组之间的最长重复子数组长度（与 “1143. 最长公共子序列” 的状态定义差别）
  • 递推公式

    • 当前数字相等，dp[j] = dp[i-1][j-1] + 1
    • 当前数字不相等，dp[j] = 0

53. 最大子序和

题目链接
  1. class Solution:
  2.     def maxSubArray(self, nums: List[int]) -> int:
  3.         n = len(nums)
  4.         dp = [-inf for _ in range(n + 1)]
  5.         res = -inf
  6.         for i in range(1, n + 1):
  7.             dp[i] = max(nums[i-1], dp[i-1] + nums[i-1])
  8.             res = max(res, dp[i])
  9.         return res
复制代码


  • 状态定义：dp 表现以 num[i-1] 末端的最大子序列和
  • 递推公式：dp = max(nums[i-1], dp[i-1] + nums[i-1])，不继承 / 继承之前的序列和
  • 初始化：额外增加一个状态位，默认初始化为 -inf
编辑间隔

392. 判定子序列

题目链接
  1. class Solution:
  2.     def isSubsequence(self, s: str, t: str) -> bool:
  3.         m, n = len(s), len(t)
  4.         dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
  5.         for i in range(1, m + 1):
  6.             for j in range(1, n + 1):
  7.                 if s[i-1] == t[j-1]:
  8.                     dp[i][j] = dp[i-1][j-1] + 1
  9.                 else:
  10.                     dp[i][j] = dp[i][j-1]
  11.         return dp[m][n] == m
复制代码


  • 与 “1143. 最长公共子序列” 根本雷同
  • 递推公式：当元素不相等时，题目要判定 s 是否为 t 的子序列，因此 s 的元素不能缺失，故 dp[j] = max(dp[i-1][j], dp[j-1]) 可优化为 dp[j] = dp[j-1]
  • 返回值：最长公共子序列是否与 s 的长度雷同
  • 另：双指针法更为简单
115. 差别的子序列

题目链接
  1. class Solution:
  2.     def numDistinct(self, s: str, t: str) -> int:
  3.         m, n = len(s), len(t)
  4.         if m < n:
  5.             return 0
  6.         dp = [[1] + [0] * m for _ in range(m + 1)]
  7.         for i in range(1, m + 1):
  8.             for j in range(1, n + 1):
  9.                 if s[i-1] == t[j-1]:
  10.                     dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
  11.                 else:
  12.                     dp[i][j] = dp[i-1][j]
  13.         return dp[m][n]
复制代码


  • 状态定义：dp[j] 表现考虑 s 前 i 个字符、t 前 j 个字符，差别的子序列共有多少个
  • 递推公式：

    • 当元素相等时，s 可以删也可以不删，即 dp[j] = dp[i-1][j] + dp[i-1][j-1]
    • 当元素不等时，s 必须要删除，即 dp[j] = dp[i-1][j]

  • 初始化：第一列为 1 别的列为 0
583. 两个字符串的删除

题目链接
  1. class Solution:
  2.     def minDistance(self, word1: str, word2: str) -> int:
  3.         m, n = len(word1), len(word2)
  4.         dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
  5.         for i in range(m + 1): dp[i][0] = i
  6.         for j in range(n + 1): dp[0][j] = j
  7.         for i in range(1, m + 1):
  8.             for j in range(1, n + 1):
  9.                 if word1[i-1] == word2[j-1]:
  10.                     dp[i][j] = dp[i-1][j-1]
  11.                 else:
  12.                     dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
  13.         return dp[m][n]
复制代码


  • 状态定义：dp[j] 表现考虑 s 前 i 个字符、t 前 j 个字符，最少删除字符数
  • 递推公式：

    • 当前字符相等时，不需要删除，dp[j] = dp[i-1][j-1]
    • 当前字符不相等时，删除 s 或删除 t，dp[j] = min(dp[i-1][j], dp[j-1]) + 1

  • 初始化：第一行、第一列初始化为对应字符的数量，即删除 x 个字符后变成空字符串
  • 另：本题还可通过求最长公共子序列，之后与二者长度相减，得到最少删除字符数
72. 编辑间隔

题目链接
  1. class Solution:
  2.     def minDistance(self, word1: str, word2: str) -> int:
  3.         m, n = len(word1), len(word2)
  4.         dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
  5.         for i in range(m + 1): dp[i][0] = i
  6.         for j in range(n + 1): dp[0][j] = j
  7.         for i in range(1, m + 1):
  8.             for j in range(1, n + 1):
  9.                 if word1[i-1] == word2[j-1]:
  10.                     dp[i][j] = dp[i-1][j-1]
  11.                 else:
  12.                     dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
  13.         return dp[m][n]
复制代码


  • 在上题的基础上，额外添加了替换元素，在当前字符不等的递推公式中添加 d[i-1][j-1] 即可
回文

647. 回文子串

题目链接
  1. class Solution:
  2.     def countSubstrings(self, s: str) -> int:
  3.         n = len(s)
  4.         dp = [[False for _ in range(n)] for _ in range(n)]
  5.         res = 0
  6.         for i in range(n - 1, -1, -1):
  7.             for j in range(i, n):
  8.                 if s[i] == s[j]:
  9.                     if j - i <= 1:
  10.                         dp[i][j] = True
  11.                     else:
  12.                         dp[i][j] = dp[i+1][j-1]
  13.                 else:
  14.                     dp[i][j] = False
  15.                
  16.                 if dp[i][j]: res += 1
  17.         return res
复制代码


  • 状态定义：dp[j] 表现 nums[i:j+1] 是否为回文串
  • 递推公式：

    • s == s[j] 时，如果字符串长度为 1 或 2，则 dp[j] = True，反之 dp[j] = dp[i+1][j-1]
    • s != s[j] 时，dp[j] = False

  • 统计 dp[j] 中有多少个为 True 的元素，即为答案
  • 注意遍历范围及遍历次序：

    • 范围：上三角矩阵，要包管 i <= j
    • 次序：dp 依赖于 dp[i+1]，因此 i 要倒序遍历

中心拓展法
  1. class Solution:
  2.     def countSubstrings(self, s: str) -> int:
  3.         n = len(s)
  4.         res = 0
  6.         def mid_extend(i, j):
  7.             nonlocal res
  8.             while i >= 0 and j < n and s[i] == s[j]:
  9.                 i -= 1
  10.                 j += 1
  11.                 res += 1
  13.         for i in range(n):
  14.             mid_extend(i,i)
  15.             mid_extend(i,i+1)
  16.         return res
复制代码


  • 枚举全部可能的中心，中心存在奇、偶两种情况
516.最长回文子序列

题目链接
  1. class Solution:
  2.     def longestPalindromeSubseq(self, s: str) -> int:
  3.         n = len(s)
  4.         dp = [[0 for _ in range(n)] for _ in range(n)]
  5.         for i in range(n - 1, -1, -1):
  6.             for j in range(i, n):
  7.                 if s[i] == s[j]:
  8.                     if j - i <= 1:
  9.                         dp[i][j] = j - i + 1
  10.                     else:
  11.                         dp[i][j] = dp[i+1][j-1] + 2
  12.                 else:
  13.                     dp[i][j] = max(dp[i+1][j], dp[i][j-1])
  14.         return dp[0][n-1]     
复制代码


  • 整体代码结构和上题雷同
  • 状态定义：dp[j] 表现 nums[i:j+1] 的最长回文子序列的长度
  • 递推公式：

    • s == s[j] 时，如果字符串长度为 1 或 2，则 dp[j] = j - i + 1，反之 dp[j] = dp[i+1][j-1] + 2
    • s != s[j] 时，删除 s 或 s[j]，取最大值，即 dp[j] = max(dp[i+1][j], dp[j-1])

  • 注意遍历范围及遍历次序

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/) Powered by Discuz! X3.4