代码随想录第58天(动态规划):● 392.判断子序列 ● 115.不同的子序列
一、判断子序列
题目描述:

思路和想法:
这道题目还是最长公共子序列的拓展,只是这里进行删除的一定是t字符串,当不相等时,dp[i][j] = dp[i][j - 1];其余基本一致。当最长公共子序列个数等s.size()时,返回true;● 1143.最长公共子序列
#include<string>
#include<vector>
using namespace std;class Solution {
public:bool isSubsequence(string s, string t) {if(s.size() == 0) return true;if(s.size() > t.size()) return false;vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1,0));for (int i = 1; i <= s.size(); i++){for (int j = 1; j <= t.size(); j++){if(s[i - 1] == t[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}else{//删除元素一定是t字符串dp[i][j] = dp[i][j - 1];}if(dp[i][j] == s.size()) return true;}}return false;}
};
二、不同的子序列
题目描述:

思路和想法:
(1)dp[i][j] : 以i - 1为结尾的s中有j - 1为尾的t的个数。
(2)当(s[i - 1] == j[i - 1])时,dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];当(s[i - 1] != j[i - 1])时,dp[i][j] = dp[i - 1][j]。
这里要注意dp数组的定义:
(1)vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1,0));会出现溢出的情况

(2) vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1,0));
#include<vector>
#include<string>
using namespace std;class Solution {
public:int numDistinct(string s, string t) {if(s.size() < t.size()) return 0;vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1,0));//第一行和第一列初始化for (int i = 0; i < s.size(); i++) dp[i][0] = 1; for (int j = 1; j < t.size(); j++) dp[0][j] = 0; for (int i = 1; i <= s.size(); i++){for (int j = 1; j <= t.size(); j++){if(s[i - 1] == t[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];}else{dp[i][j] = dp[i - 1][j];}}}return dp[s.size()][t.size()]; }
};
相关文章:
代码随想录第58天(动态规划):● 392.判断子序列 ● 115.不同的子序列
一、判断子序列 题目描述: 思路和想法: 这道题目还是最长公共子序列的拓展,只是这里进行删除的一定是t字符串,当不相等时,dp[i][j] dp[i][j - 1];其余基本一致。当最长公共子序列个数等s.size()时&#x…...
代码随想录第55天(动态规划):● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费
一、最佳买卖股票时机含冷冻期 题目描述: 思路和想法: 这道题相较于之前的题目,注重对状态的分析,这里分为四个状态。 (1)状态一,买入状态 dp[i][0] 操作一:前一天就是持有状态(状…...
字符串装换整数(atoi)-力扣8-java
一、题目描述请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C 中的 atoi 函数)。函数 myAtoi(string s) 的算法如下:读入字符串并丢弃无用的前导空格检查下一个字符(假设还未…...
毕业5年,从月薪3000到年薪40w,我掌握了那些核心技能?(建议收藏)
大家好,我是静静~~是一枚一线大厂的测试开发工程师很多读者私信问我,自己时间不短了,随着工作年限的不断增长,感觉自己的技术水平与自己的工作年限严重不符。想跳槽出去换个新环境吧,又感觉自己的能力达不到心仪公司的…...
C++中的并行与并发
1.1 并行基础std::thread 用于创建一个执行的线程实例,所以它是一切并发编程的基础,使用时需要包含 <thread> 头文件, 它提供了很多基本的线程操作,例如 get_id() 来获取所创建线程的线程 ID,使用 join() 来加入…...
h2database源码解析-如何更新一条行记录
这里的更新包括两种操作:删、改。更新操作涉及的内容在其他文章里面已经做过介绍了,本文主要是介绍更新的代码流程,以了解更新操作都做了哪些事情。如果有未介绍过的知识点会详细介绍。 目录改(update)如何判读是否加了行锁删(delete)改(upda…...
FyListen——生命周期监听器(设计原理之理解生命周期)
FyListen——生命周期监听器(设计原理之理解生命周期) FyListen 的核心原理有两个: 通过子Fragment对Activity、Fragment进行生命周期监听Java8 接口特性 default 1. 什么是上下文Context 这是一个装饰器模式, ContextImpl 是 …...
Element UI框架学习篇(六)
Element UI框架学习篇(六) 1 删除数据 1.1 前台核心函数 1.1.1 elementUI中的消息提示框语法 //①其中type类型和el-button中的type类型是一致的,有info灰色,success绿色,danger红色,warning黄色,primary蓝色 //②message是你所要填写的提示信息 //③建议都用,因为比双引号…...
Python如何安装模块,python模块安装失败的原因以及解决办法
前言 今天来给刚开始学习python的朋友讲解一下 如何安装python模块, python模块安装失败的原因以及解决办法 很多朋友拿到代码之后,就开始复制粘贴 --> 然后右键进行运行 结果就是报错说 没有这个模块 得安装啥的 Python模块安装 一. 打开命令提示符 win …...
《NFL橄榄球》:洛杉矶闪电·橄榄1号位
洛杉矶闪电(英语:Los Angeles Chargers),又译“洛杉磯衝鋒者”。是一支位于加利福尼亚州洛杉矶郡英格尔伍德的职业美式橄榄球球队,现为美国橄榄球联合会西区成员之一。该队曾于1961年搬迁到圣地亚哥而改叫圣地亚哥电光…...
4.7 Python设置代码格式
随着你编写的程序越来越长,有必要了解一些代码格式设置约定。请花时让你的代码尽可能易于阅读;让代码易于阅读有助于你掌握程序是做什么的,也可以帮助他人理解你编写的代码。为确保所有人编写的代码的结构都大致一致,Python程序员都遵循一些格…...
Zabbix 构建监控告警平台(五)
Zabbix 自动发现Zabbix 自动注册1.Zabbix 自动发现 1.1前言 为了满足监控企业成千上万台服务器,因此我们需要使用Zabbix批量监控来实现。自动发现和自动注册。 1.2zabbix-server (一)1、创建自动发现规则 在“配置”->“自动发现”->“…...
2023关键词:挑战
未失踪人口回归… 好久不见,不经意间拖更2个多月。今天周末,外面淅淅沥沥下着小雨,这种窝在床上的时刻最适合写点东西了。 但是建议大家在办公或者写博客的时候尽量还是端正坐姿,我就是因为喜欢这样靠在床背上,长时间…...
Wifi wpa_supplicant 到驱动的联系
同学,别退出呀,我可是全网最牛逼的 WIFI/BT/GPS/NFC分析博主,我写了上百篇文章,请点击下面了解本专栏,进入本博主主页看看再走呗,一定不会让你后悔的,记得一定要去看主页置顶文章哦。 从framework到wpa_supplicant的适配层,其中framework部分需要了注意的是wifiservic…...
【状态估计】基于二进制粒子群优化 (BPSO) 求解最佳 PMU优化配置研究【IEEE30、39、57、118节点】(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
python 将 .pdf 文件转为 .md
环境准备 pip install aspose-words 代码 doc aw.Document(r"pdf 文件路径\xxx.pdf") doc.save("Output.md") 来源:https://products.aspose.com/words/zh/python-net/conversion/...
【C语言】操作符详解
每天一篇博客,卷死各位。 文章目录前言1. 算术操作符2. 移位进制位的表示移位操作符1. 》--左移操作符2. 《--右移操作符3.位操作符4.赋值操作符5.单目操作符6.关系操作符7. 逻辑操作符8.条件操作符9.逗号操作符总结前言 在c语言学习中操作符尤为重要,而…...
微信小程序 学生选课系统--nodejs+vue
系统分为学生和管理员,教师三个角色 学生小程序端的主要功能有: 1.用户注册和登陆系统 2.查看选课介绍信息 3.查看查看课程分类 4.查看课程详情,在线选课,提交选课信息 5.在线搜索课程信息 6.用户个人中心修改个人资料 7.用户查看…...
leaflet 加载geojson文件并显示图形(示例代码051)
第051个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+leaflet中加载geojson文件,将图形显示在地图上。 直接复制下面的 vue+openlayers源代码,操作2分钟即可运行实现效果; 注意如果OpenStreetMap无法加载,请加载其他来练习 文章目录 示例效果配置方式示例源代码(…...
【Kafka】ZK和Kafka集群的安装和配置
一、集群环境说明1. 虚拟机:192.168.223.101/103/1052. 系统版本:CentOS 7.93. JDK版本:11.0.18.0.14. Zookeeper版本:3.7.15. Kafka版本:2.13-2.8.2备注:无论是ZK,还是Kafka,都需要…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
