【LeetCode 刷题】动态规划(5)-子序列题目

铁佛  论坛元老 | 2025-3-30 08:43:32 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 1910|帖子 1910|积分 5730

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要 登录 才可以下载或查看，没有账号？立即注册

x
此博客为《代码随想录》动态规划章节的学习条记，主要内容为动态规划子序列题目的相干题目剖析。

   
  不连续子序列

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
复制代码


  • 状态定义：dp 表现以 num 末端的最长递增子序列的长度
  • 递推公式：dp = max(dp, dp[j] + 1)，dp 可以由前面恣意位置转移而来，取最大值
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企服之家，中国第一个企服评测及商务社交产业平台。
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

铁佛

论坛元老
这个人很懒什么都没写!

楼主热帖

标签云

渠道 国产数据库 集成商 AI 运维 CIO 存储 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表