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

每天一道leetcode:115. 不同的子序列(动态规划困难)

今日份题目:

给你两个字符串 st ,统计并返回在 s子序列t 出现的个数。

题目数据保证答案符合 32 位带符号整数范围。

示例1

输入:s = "rabbbit", t = "rabbit"
输出:3
解释:
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit选前两个b
rabbbit选后两个b
rabbbit选两头的b

示例2

输入:s = "babgbag", t = "bag"
输出:5

提示

  • 1 <= s.length, t.length <= 1000

  • st 由英文字母组成

题目思路

这道题目的思路和之前的子序列的思路不太一样的地方在于,这道题用到的是当前位置到字符串最后位置的子问题,而之前的题是当前位置到开头位置的子问题。

状态转移方程:

当 s[i]=t[j] 时,dp [ i ] [ j ]由两部分组成:

如果 s[i]和 t[j]匹配,则考虑 t[j+1:] 作为 s[i+1:]的子序列,子序列数为 dp [ i+1 ] [ j+1 ];

如果 s[i] 不和 t[j] 匹配,则考虑 t[j:] 作为 s[i+1:]的子序列,子序列数为 dp [ i+1 ] [ j ]。

因此当 s[i]=t[j] 时,有 dp [ i ] [ j ] =dp [ i+1 ] [ j+1 ]+dp[ i+1 ] [ j ]。

当 s[i]≠t[j] 时,s[i]不能和 t[j]匹配,因此只考虑 t[j:]作为 s[i+1:] 的子序列,子序列数为 dp[i+1] [j]。

因此当 s[i]≠t[j] 时,有 dp [ i ] [ j ]=dp [ i+1 ] [ j ]。

得状态转移总方程:

这道题目好难,我也是有点晕,如果大家有疑问,欢迎评论区讨论哦!

代码

class Solution 
{
public:int numDistinct(string s, string t) {//获取两个字符串的长度int n= s.length();int m= t.length();if (n<m) return 0;unsigned long long dp[2000][2000]={0};//初始化边界数值for(int i=0;i<=n;i++)//此时t[m->末尾]为空字符串,故对于任何字符串,空字符串都是其子序列,为1 {dp[i][m]=1;}//更新所有dp值for(int i=n-1;i>=0;i--) {char sc=s[i];for(int j=m-1;j>=0;j--) {char tc=t[j];if(sc==tc) {dp[i][j]=dp[i+1][j+1]+dp[i+1][j];} else {dp[i][j]=dp[i+1][j];}}}return dp[0][0];}
};

提交结果

 欢迎大家在评论区讨论,如有不懂的代码部分,欢迎在评论区留言!

相关文章:

每天一道leetcode:115. 不同的子序列(动态规划困难)

今日份题目&#xff1a; 给你两个字符串 s 和 t &#xff0c;统计并返回在 s 的 子序列 中 t 出现的个数。 题目数据保证答案符合 32 位带符号整数范围。 示例1 输入&#xff1a;s "rabbbit", t "rabbit" 输出&#xff1a;3 解释&#xff1a; 如下所…...

服务器数据恢复-RAID5多块磁盘离线导致崩溃的数据恢复案例

服务器数据恢复环境&#xff1a; DELL POWEREDGE某型号服务器中有一组由6块SCSI硬盘组建的RAID5阵列&#xff0c;LINUX REDHAT操作系统&#xff0c;EXT3文件系统&#xff0c;存放图片文件。 服务器故障&分析&#xff1a; 服务器raid5阵列中有一块硬盘离线&#xff0c;管理员…...

NO.2 MyBatis框架:创建Mapper接口和映射文件,实现基本增删改查

目录 1、Mapper接口和映射文件关系 2、Mapper接口和映射文件的命名规则 2.1 Mapper接口的命名规则 2.2 映射文件的命名规则 3、Mapper接口和映射文件的创建及增删改查的实现 3.1 Mapper接口和映射文件的创建 3.2 增删改查的实现 3.2.1表结构 3.2.2 创建表User对应的实…...

【JS】怎么提取object类的内容

需求&#xff1a;在网页端中通过getElementsByClassName获取到一个元素&#xff0c;想提取其中的数字内容做个if判断&#xff0c;奈何一直提取不了 开始获取元素时&#xff0c;以为默认就是字符类型&#xff1b;但使用操作字符的函数就失败&#xff0c;然后就考虑数据类型是不是…...

分布式系统的 38 个知识点

天天说分布式分布式&#xff0c;那么我们是否知道什么是分布式&#xff0c;分布式会遇到什么问题&#xff0c;有哪些理论支撑&#xff0c;有哪些经典的应对方案&#xff0c;业界是如何设计并保证分布式系统的高可用呢&#xff1f; 1. 架构设计 这一节将从一些经典的开源系统架…...

机器学习基础(二)

线性回归 误差是独立并且具有相同的分布通常认为服从均值为0方差为的高斯分布。 损失函数(loss Function)/代价函数(Cost Function) 其实两种叫法都可以,损失函数(loss function)或代价函数(cost function)是将随机事件或其有关随机变量的取值映射为非负实数以表示该随…...

Java 实现Rtsp 转rtmp,hls,flv

服务支撑&#xff1a;FFmpeg srs(流媒体服务器) 整个流程是 FFmpeg 收流转码 推 rtmp 到流媒体服务 流媒体服务再 分发流到公网 搭建流媒体服务: 1. SRS (Simple Realtime Server) | SRS &#xff08;本例子使用的是SrS 安装使用docker &#xff09; 2.GitHub - ZLMedi…...

机器学习基础(三)

逻辑回归 场景 垃圾邮件分类 预测肿瘤是良性还是恶性 预测某人的信用是否良好 正确率与召回率 正确率与召回率(Precision & Recall)是广泛应用于信息检索和统计学分类领域的两个度量值,用来评价结果的质量。 一般来说,正确率就是检索出来的条目有多少是正确的,召回率就…...

Kubeadm安装K8s集群

一、硬件环境 准备3台Linux服务器&#xff0c;此处用Vmware虚拟机。 主机名CPU内存k8smaster2核4Gk8snode12核4Gk8snode22核4G 二、系统前置准备 配置三台主机的hosts文件 cat << EOF > /etc/hosts 192.168.240.130 k8smaster 192.168.240.132 k8snode1 192.168.…...

【C++】开源:spdlog跨平台日志库配置使用

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍spdlog日志库配置使用。 无专精则不能成&#xff0c;无涉猎则不能通。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关注一下&#xff0c;下…...

[Azkaban] No active executors found

没有找到活动的executors&#xff0c;需在MySQL数据库里设置端口为12321的executors表的active为1&#xff1a; select * from executors;如果显示active0 则需要进行处理&#xff1a; update azkaban.executors set active1;当active0&#xff0c;更新为1时&#xff0c;用 n…...

无涯教程-Perl - recv函数

描述 This function receives a message on SOCKET attempting to read LENGTH bytes, placing the data read into variable SCALAR.The FLAGS argument takes the same values as the recvfrom( ) system function, on which the function is based. When communicating wit…...

算法练习-搜索 相关

文章目录 迷宫问题 迷宫问题 定义一个二维数组 m行 * n列 &#xff0c;如 4 5 数组下所示&#xff1a; int arr[5][5] { 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, }; 它表示一个迷宫&#xff0c;1表示墙壁&#xff0c;0表示可以走的路&#xff0c;只…...

PyQt5控件布局管理

Qt Designer提供了四种窗口布局&#xff1a;Vertical Layout(垂直布局) &#xff0c;Horizontal Layout(水平布局)&#xff0c;Grid Layout(栅格布局)&#xff0c;Form Layout(表单布局)&#xff0c;以及一种隐藏的布局—绝对布局 一般进行布局有两种方式&#xff1a; 一是通…...

TypeScript 一分钟让你理解泛型是什么

TypeScript 一分钟让你理解 泛型是什么 TS的泛型是指在定义函数、接口或类型时&#xff0c;不预先指定具体的类型&#xff0c;而是在使用时指定类型限制的一种特性。 泛型和函数中的参数比较类似&#xff0c;我们定义一个函数的时候有时会给它留一个参数名&#xff0c;在使用这…...

PatchMatchNet 训练dtu数据集、训练曲线查看、实操教程图图文详解、

文章目录 1 查看要求 下载数据集2 训练2.1 路径配置2.2 训练2.3 模型输出 与 训练曲线查看2.4 输出训练 log文件1 查看要求 下载数据集 在代码文件加下打开 README.md文件找到训练说明,查看那要求、下载训练集、训练方法 ## Training Download pre-processed [DTUs trainin…...

怎样制定测试计划和设计测试用例?

测试工作贯穿于整个软件开发生命周期&#xff0c;是一项庞大而复杂的工作&#xff0c;需要制订一个完整且详细的测试计划作为指导。测试计划是整个测试工作的导航图&#xff0c;但它并不是一成不变的&#xff0c;随着项目推进或需求变更&#xff0c;测试计划也会不断发生改变&a…...

教你如何为博客网站申请阿里云的免费域名HTTPS证书

如何为博客网站申请阿里云的免费域名HTTPS证书 文章目录 如何为博客网站申请阿里云的免费域名HTTPS证书前置条件&#xff1a;步骤1 例如阿里云控制台&#xff0c;选择SSL证书步骤2 申请购买免费证书步骤3 创建证书步骤3.1 证书申请步骤3.2 DNS域名验证 步骤4 等待证书审核成功&…...

在线Word怎么转换成PDF?Word无法转换成PDF文档原因分析

不同的文件格式使用方法是不一样的&#xff0c;而且也需要使用不同的工具才可以打开编辑内容&#xff0c;针对不同的场合用户们难免会用到各种各样的文件格式&#xff0c;要想在不修改内容的前提下提高工作效率&#xff0c;那就需要用到文件格式转换&#xff0c;那么在线Word怎…...

计算机网络:网络通信相关概念入门

目录 一、网络发展背景二、理解网络通信三、理解IP地址1.简述IP地址2.IP地址的版本3.提高地址利用率的技术 四、理解端口1.简述端口2.使用端口的原因 五、理解网络通信协议 一、网络发展背景 网络发展背景&#xff1a; 最初的计算机是单机&#xff0c;那么单机是这样传输数据的…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...