每天一道leetcode:115. 不同的子序列(动态规划困难)
今日份题目:
给你两个字符串 s 和 t ,统计并返回在 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 -
s和t由英文字母组成
题目思路
这道题目的思路和之前的子序列的思路不太一样的地方在于,这道题用到的是当前位置到字符串最后位置的子问题,而之前的题是当前位置到开头位置的子问题。
状态转移方程:
当 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. 不同的子序列(动态规划困难)
今日份题目: 给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数。 题目数据保证答案符合 32 位带符号整数范围。 示例1 输入:s "rabbbit", t "rabbit" 输出:3 解释: 如下所…...
服务器数据恢复-RAID5多块磁盘离线导致崩溃的数据恢复案例
服务器数据恢复环境: DELL POWEREDGE某型号服务器中有一组由6块SCSI硬盘组建的RAID5阵列,LINUX REDHAT操作系统,EXT3文件系统,存放图片文件。 服务器故障&分析: 服务器raid5阵列中有一块硬盘离线,管理员…...
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类的内容
需求:在网页端中通过getElementsByClassName获取到一个元素,想提取其中的数字内容做个if判断,奈何一直提取不了 开始获取元素时,以为默认就是字符类型;但使用操作字符的函数就失败,然后就考虑数据类型是不是…...
分布式系统的 38 个知识点
天天说分布式分布式,那么我们是否知道什么是分布式,分布式会遇到什么问题,有哪些理论支撑,有哪些经典的应对方案,业界是如何设计并保证分布式系统的高可用呢? 1. 架构设计 这一节将从一些经典的开源系统架…...
机器学习基础(二)
线性回归 误差是独立并且具有相同的分布通常认为服从均值为0方差为的高斯分布。 损失函数(loss Function)/代价函数(Cost Function) 其实两种叫法都可以,损失函数(loss function)或代价函数(cost function)是将随机事件或其有关随机变量的取值映射为非负实数以表示该随…...
Java 实现Rtsp 转rtmp,hls,flv
服务支撑:FFmpeg srs(流媒体服务器) 整个流程是 FFmpeg 收流转码 推 rtmp 到流媒体服务 流媒体服务再 分发流到公网 搭建流媒体服务: 1. SRS (Simple Realtime Server) | SRS (本例子使用的是SrS 安装使用docker ) 2.GitHub - ZLMedi…...
机器学习基础(三)
逻辑回归 场景 垃圾邮件分类 预测肿瘤是良性还是恶性 预测某人的信用是否良好 正确率与召回率 正确率与召回率(Precision & Recall)是广泛应用于信息检索和统计学分类领域的两个度量值,用来评价结果的质量。 一般来说,正确率就是检索出来的条目有多少是正确的,召回率就…...
Kubeadm安装K8s集群
一、硬件环境 准备3台Linux服务器,此处用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跨平台日志库配置使用
😏★,:.☆( ̄▽ ̄)/$:.★ 😏 这篇文章主要介绍spdlog日志库配置使用。 无专精则不能成,无涉猎则不能通。——梁启超 欢迎来到我的博客,一起学习,共同进步。 喜欢的朋友可以关注一下,下…...
[Azkaban] No active executors found
没有找到活动的executors,需在MySQL数据库里设置端口为12321的executors表的active为1: select * from executors;如果显示active0 则需要进行处理: update azkaban.executors set active1;当active0,更新为1时,用 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列 ,如 4 5 数组下所示: int arr[5][5] { 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, }; 它表示一个迷宫,1表示墙壁,0表示可以走的路,只…...
PyQt5控件布局管理
Qt Designer提供了四种窗口布局:Vertical Layout(垂直布局) ,Horizontal Layout(水平布局),Grid Layout(栅格布局),Form Layout(表单布局),以及一种隐藏的布局—绝对布局 一般进行布局有两种方式: 一是通…...
TypeScript 一分钟让你理解泛型是什么
TypeScript 一分钟让你理解 泛型是什么 TS的泛型是指在定义函数、接口或类型时,不预先指定具体的类型,而是在使用时指定类型限制的一种特性。 泛型和函数中的参数比较类似,我们定义一个函数的时候有时会给它留一个参数名,在使用这…...
PatchMatchNet 训练dtu数据集、训练曲线查看、实操教程图图文详解、
文章目录 1 查看要求 下载数据集2 训练2.1 路径配置2.2 训练2.3 模型输出 与 训练曲线查看2.4 输出训练 log文件1 查看要求 下载数据集 在代码文件加下打开 README.md文件找到训练说明,查看那要求、下载训练集、训练方法 ## Training Download pre-processed [DTUs trainin…...
怎样制定测试计划和设计测试用例?
测试工作贯穿于整个软件开发生命周期,是一项庞大而复杂的工作,需要制订一个完整且详细的测试计划作为指导。测试计划是整个测试工作的导航图,但它并不是一成不变的,随着项目推进或需求变更,测试计划也会不断发生改变&a…...
教你如何为博客网站申请阿里云的免费域名HTTPS证书
如何为博客网站申请阿里云的免费域名HTTPS证书 文章目录 如何为博客网站申请阿里云的免费域名HTTPS证书前置条件:步骤1 例如阿里云控制台,选择SSL证书步骤2 申请购买免费证书步骤3 创建证书步骤3.1 证书申请步骤3.2 DNS域名验证 步骤4 等待证书审核成功&…...
在线Word怎么转换成PDF?Word无法转换成PDF文档原因分析
不同的文件格式使用方法是不一样的,而且也需要使用不同的工具才可以打开编辑内容,针对不同的场合用户们难免会用到各种各样的文件格式,要想在不修改内容的前提下提高工作效率,那就需要用到文件格式转换,那么在线Word怎…...
计算机网络:网络通信相关概念入门
目录 一、网络发展背景二、理解网络通信三、理解IP地址1.简述IP地址2.IP地址的版本3.提高地址利用率的技术 四、理解端口1.简述端口2.使用端口的原因 五、理解网络通信协议 一、网络发展背景 网络发展背景: 最初的计算机是单机,那么单机是这样传输数据的…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
MySQL的pymysql操作
本章是MySQL的最后一章,MySQL到此完结,下一站Hadoop!!! 这章很简单,完整代码在最后,详细讲解之前python课程里面也有,感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...
消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...
嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)
目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 编辑编辑 UDP的特征 socke函数 bind函数 recvfrom函数(接收函数) sendto函数(发送函数) 五、网络编程之 UDP 用…...
JS面试常见问题——数据类型篇
这几周在进行系统的复习,这一篇来说一下自己复习的JS数据结构的常见面试题中比较重要的一部分 文章目录 一、JavaScript有哪些数据类型二、数据类型检测的方法1. typeof2. instanceof3. constructor4. Object.prototype.toString.call()5. type null会被判断为Obje…...
