当前位置: 首页 > 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]

相关文章:

动态规划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&#x…...

APP UI自动化测试思路总结

首先想要说明一下,APP自动化测试可能很多公司不用,但也是大部分自动化测试工程师、高级测试工程师岗位招聘信息上要求的,所以为了更好的待遇,我们还是需要花时间去掌握的,毕竟谁也不会跟钱过不去。 接下来&#xff0c…...

Codeforces Round 936 (Div. 2)

C. Tree Cutting 题意&#xff1a;给定一棵树&#xff0c;需要删除 k 条边&#xff0c;使得 k1 个联通块中的最小结点数最大。求出这个最大值 思路&#xff1a;求最小值最大--想到二分答案--然后深搜满足条件的连通块是否大于k即可 #include<iostream> #include<al…...

yolov6实现遥感影像目标识别|以DIOR数据集为例

1 目标检测是计算机视觉领域中的一项重要任务&#xff0c;它的目标是在图像或视频中检测出物体的位置和类别。YOLO&#xff08;You Only Look Once&#xff09;是一系列经典的目标检测算法&#xff0c;最初由Joseph Redmon等人于2016年提出。YOLO算法具有快速、简单、端到端的特…...

stable-diffusion-electron-clickstart 支持windows AMD显卡

前言 使用vue3 vite electron element-plus构建&#xff0c;正好学习下electrongithub stable-diffusion “画境导航者” 启动器 简介 stable-diffusion “画境导航者” 启动器支持功能 一键启动打开文件夹&#xff08;tmp、txt2img-images&#xff09;等模型所在文件夹&…...

ES进程除了kill之外,有什么优雅关闭的方式吗?

问题 Linux环境中&#xff0c;Elasticsearch 8的进程除了kill之外&#xff0c;有什么优雅关闭的方式吗&#xff1f; 具体实施方式 在Linux环境中&#xff0c;Elasticsearch&#xff08;ES&#xff09;进程可以通过多种方式实现优雅关闭&#xff0c;这种方式允许它完成必要的…...

院子摄像头的监控

院子摄像头的监控和禁止区域入侵检测相比&#xff0c;多了2个功能&#xff1a;1&#xff09;如果检测到有人入侵&#xff0c;则把截图保存起来&#xff0c;2&#xff09;如果检测到有人入侵&#xff0c;则向数据库插入一条事件数据。 打开checkingfence.py&#xff0c;添加如下…...

SpringBoot3使用响应Result类返回的响应状态码为406

Resolved [org.springframework.web.HttpMediaTypeNotAcceptableException: No acceptable representation] 解决方法&#xff1a;Result类上加上Data注解...

基础:TCP四次挥手做了什么,为什么要挥手?

1. TCP 四次挥手在做些什么 1. 第一次挥手 &#xff1a; 1&#xff09;挥手作用&#xff1a;主机1发送指令告诉主机2&#xff0c;我没有数据发送给你了。 2&#xff09;数据处理&#xff1a;主机1&#xff08;可以是客户端&#xff0c;也可以是服务端&#xff09;&#xff0c…...

Android Studio实现内容丰富的安卓校园二手交易平台(带聊天功能)

获取源码请点击文章末尾QQ名片联系&#xff0c;源码不免费&#xff0c;尊重创作&#xff0c;尊重劳动 项目编号083 1.开发环境android stuido jdk1.8 eclipse mysql tomcat 2.功能介绍 安卓端&#xff1a; 1.注册登录 2.查看二手商品列表 3.发布二手商品 4.商品详情 5.聊天功能…...

第十一届蓝桥杯省赛第一场真题

2065. 整除序列 - AcWing题库 #include <bits/stdc.h> using namespace std; #define int long long//记得开long long void solve(){int n;cin>>n;while(n){cout<<n<< ;n/2;} } signed main(){int t1;while(t--)solve();return 0; } 2066. 解码 - …...

设计模式 模板方法模式

01.如果接到一个任务&#xff0c;要求设计不同型号的悍马车 02.设计一个悍马车的抽象类&#xff08;模具&#xff0c;车模&#xff09; public abstract class HummerModel {/** 首先&#xff0c;这个模型要能够被发动起来&#xff0c;别管是手摇发动&#xff0c;还是电力发动…...

【STM32嵌入式系统设计与开发】——6矩阵按键应用(4x4)

这里写目录标题 一、任务描述二、任务实施1、SingleKey工程文件夹创建2、函数编辑&#xff08;1&#xff09;主函数编辑&#xff08;2&#xff09;LED IO初始化函数(LED_Init())&#xff08;3&#xff09;开发板矩阵键盘IO初始化&#xff08;ExpKeyBordInit()&#xff09;&…...

乐优商城(九)数据同步RabbitMQ

1. 项目问题分析 现在项目中有三个独立的微服务&#xff1a; 商品微服务&#xff1a;原始数据保存在 MySQL 中&#xff0c;从 MySQL 中增删改查商品数据。搜索微服务&#xff1a;原始数据保存在 ES 的索引库中&#xff0c;从 ES 中查询商品数据。商品详情微服务&#xff1a;做…...

XSS-labs详解

xss-labs下载地址https://github.com/do0dl3/xss-labs 进入靶场点击图片&#xff0c;开始我们的XSS之旅&#xff01; Less-1 查看源码 代码从 URL 的 GET 参数中取得 "name" 的值&#xff0c;然后输出一个居中的标题&#xff0c;内容是 "欢迎用户" 后面…...

设计模式——模板方法模式封装.net Core读取不同类型的文件

1、模板方法模式 模板方法模式&#xff1a;定义一个操作中的算法骨架&#xff0c;而将一些步骤延迟到子类中&#xff0c;模板方法使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。 特点&#xff1a;通过把不变的行为搬移到超类&#xff0c;去除子类中重复的代…...

[思考记录]技术欠账

最近对某开发项目做回顾梳理&#xff0c;除了进一步思考整理相关概念和问题外&#xff0c;一个重要的任务就是清理“技术欠账”。 这个“技术欠账”是指在这个项目的初期&#xff0c;会有意无意偏向快速实现&#xff0c;想先做出来、用起来&#xff0c;进而在实现过程中做出…...

React - 实现菜单栏滚动

简介 本文将会基于react实现滚动菜单栏功能。 技术实现 实现效果 点击菜单&#xff0c;内容区域会自动滚动到对应卡片。内容区域滑动&#xff0c;指定菜单栏会被选中。 ScrollMenu.js import {useRef, useState} from "react"; import ./ScrollMenu.css;export co…...

线性筛选(欧拉筛选)-洛谷P3383

#include <bits/stdc.h> using namespace std; int main() {std::ios::sync_with_stdio(false); cin.tie(nullptr); //为了加速int n, q;cin >> n >> q; vector<int>num(n 1); //定义数字表vector<int>prime; //定义素数表数组num[1] …...

企业微信可以更换公司主体吗?

企业微信变更主体有什么作用&#xff1f;当我们的企业因为各种原因需要注销或已经注销&#xff0c;或者运营变更等情况&#xff0c;企业微信无法继续使用原主体继续使用时&#xff0c;可以申请企业主体变更&#xff0c;变更为新的主体。企业微信变更主体的条件有哪些&#xff1…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...

DiscuzX3.5发帖json api

参考文章&#xff1a;PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下&#xff0c;适配我自己的需求 有一个站点存在多个采集站&#xff0c;我想通过主站拿标题&#xff0c;采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...