当前位置: 首页 > news >正文

动态规划15 | ● 392.判断子序列 ● *115.不同的子序列

392.判断子序列

https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html

  • 考点
    • 子序列问题
  • 我的思路
    • dp[i][j]的含义是,两个序列分别取到下标为i和j的时候,他们是否满足前者是后者的子序列,满足为True,否则为False
    • 递推公式,分为后者序列取到第j - 1个元素时就已经满足前者序列为其子序列的情况、dp[i - 1][j - 1]满足子序列要求且前者序列的第i个元素和后者序列的第j个元素恰好相等的情况、以及dp[i][j]不满足为子序列的情况
    • 初始化,建议画出二维矩阵,并举一个例子来分析,仅额外初始化后者序列对应的第一条边即可(将所有满足子序列要求的位置设置为True),其与都为False
  • 视频讲解关键点总结
    • 和我的思路不太一样
  • 我的思路的问题
  • 代码书写问题
  • 可执行代码
class Solution:def isSubsequence(self, s: str, t: str) -> bool:if s == '':return Trueelif t == '':return Falsedp = [[False] * len(t) for _ in range(len(s))]for i in range(len(t)):if t[i] == s[0]:for j in range(i, len(t)):dp[0][j] = Truebreakfor i in range(1, len(s)):for j in range(1, len(t)):if dp[i][j - 1]:dp[i][j] = Trueelif s[i] == t[j] and dp[i - 1][j - 1]:dp[i][j] = Truereturn dp[-1][-1]

*115.不同的子序列

https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html

  • 考点
    • 子序列问题
  • 我的思路
    • 无思路
  • 视频讲解关键点总结
    • 明确本题的目标,我们是要在后者元素中删除元素获得子序列来让该子序列与前者序列相同
    • dp[i][j]的含义是,两个序列分别取到下标为i和j的时候,后者序列能组合出多少种和前者序列相同的子序列
    • 递推公式,如果当前下标的元素相同,则可以同时取当前下标元素(此时dp[i][j] = dp[i - 1][j - 1])或者不取后者序列的当前元素(此时dp[i][j] = dp[i][j - 1]);如果当前下标的元素不相同,则只有dp[i][j] = dp[i][j - 1]
    • 初始化,建议画出二维矩阵,并举一个例子来分析,仅额外初始化后者序列对应的第一条边即可
  • 我的思路的问题
    • 无思路
  • 代码书写问题
  • 可执行代码
class Solution:def numDistinct(self, s: str, t: str) -> int:dp = [[0] * len(s) for _ in range(len(t))]if s[0] == t[0]:dp[0][0] = 1for i in range(1, len(s)):if t[0] == s[i]:dp[0][i] = dp[0][i - 1] + 1else:dp[0][i] = dp[0][i - 1]for i in range(1, len(t)):for j in range(1, len(s)):if s[j] == t[i]:dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]else:dp[i][j] = dp[i][j - 1]return dp[-1][-1]
http://www.lryc.cn/news/323985.html

相关文章:

  • APP UI自动化测试思路总结
  • Codeforces Round 936 (Div. 2)
  • yolov6实现遥感影像目标识别|以DIOR数据集为例
  • stable-diffusion-electron-clickstart 支持windows AMD显卡
  • ES进程除了kill之外,有什么优雅关闭的方式吗?
  • 院子摄像头的监控
  • SpringBoot3使用响应Result类返回的响应状态码为406
  • 基础:TCP四次挥手做了什么,为什么要挥手?
  • Android Studio实现内容丰富的安卓校园二手交易平台(带聊天功能)
  • 第十一届蓝桥杯省赛第一场真题
  • 设计模式 模板方法模式
  • 【STM32嵌入式系统设计与开发】——6矩阵按键应用(4x4)
  • 乐优商城(九)数据同步RabbitMQ
  • XSS-labs详解
  • 设计模式——模板方法模式封装.net Core读取不同类型的文件
  • [思考记录]技术欠账
  • React - 实现菜单栏滚动
  • 线性筛选(欧拉筛选)-洛谷P3383
  • 企业微信可以更换公司主体吗?
  • Qt教程 — 3.6 深入了解Qt 控件:Display Widgets部件(2)
  • Golang案例开发之gopacket抓包三次握手四次分手(3)
  • 如何减少pdf的文件大小?pdf压缩工具介绍
  • TypeScript基础类型
  • 长安链智能合约标准协议第二草案——BNS与DID协议邀请社区用户评审
  • 安防监控视频汇聚平台EasyCVR接入海康Ehome设备,设备在线但视频无法播放是什么原因?
  • 【Python + Django】表结构创建
  • 解锁编程潜能:ChatGPT如何革新软件开发
  • 内网使用rustdesk进行远程协助
  • linux内核input子系统概述
  • 【解决报错】vi/vim修改文件时报错:Found a swap file by the name xxxxx