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

力扣-动态规划-115 不同子序列

思路

  1. dp数组定义:0_i-1的字符串中有0_j-1的字符串有dp[i][j]个
  2. 递推公式:
    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];
    }

    在该元素相同时,有两种可能1:使用该元素,所以0_i-2中有多少个0_j-2,这样再加上i-1和j-1,这满足了0_i-1的字符串中有0_j-1的字符串;第二种可能,不使用该元素,直接看0_i-2的字符串中有0_j-1的字符串            不相同时,只能不用i-1,要跳过i-1,所以沿用前一个结果

  3. dp数组初始化:for(int i = 0; i <= s.size(); i++) dp[i][0] = 1;
  4. 遍历顺序:顺序
  5. 时间复杂度:      O(n*m)

代码

class Solution {
public:int numDistinct(string s, string t) {long long mod = 10E9 + 7;vector< vector<long long>> dp(s.size() + 1, vector<long long>(t.size() + 1, 0));for(int i = 0; i <= s.size(); i++) dp[i][0] = 1;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()];}
};  

相关文章:

力扣-动态规划-115 不同子序列

思路 dp数组定义&#xff1a;0_i-1的字符串中有0_j-1的字符串有dp[i][j]个递推公式&#xff1a; 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]; } 在该元素相同时&#xff0c;有两种可能1&#xff1a;使用该元素&#xff0c;所以0_i-2…...

Qt C++ 开发 动态上下页按钮实现

项目开发&#xff0c;想实现动态的显示按钮&#xff0c;考虑使用QStackedWidget做两个页面去切换。 首先&#xff0c;我们使用Qt ui 画出两个QStackedWidget的两个页面 要实现切换&#xff0c;我们只需要调用stackedWidget->setCurrentIndex(index)就行。 那么如何自动调…...

数据结构第五节:排序

1.常见的排序算法 插入排序&#xff1a;直接插入排序、希尔排序 选择排序&#xff1a;直接选择排序、堆排序 交换排序&#xff1a;冒泡排序、快速排序 归并排序&#xff1a;归并排序 排序的接口实现&#xff1a; // 1. 直接插入排序 void InsertSort(int* a, int n); // 2. 希…...

从文件到块: 提高 Hugging Face 存储效率

Hugging Face 在Git LFS 仓库中存储了超过30 PB 的模型、数据集和 Spaces。由于 Git 在文件级别进行存储和版本控制&#xff0c;任何文件的修改都需要重新上传整个文件。这在 Hub 上会产生高昂的成本&#xff0c;因为平均每个 Parquet 和 CSV 文件大小在 200-300 MB 之间&#…...

Android14 串口控制是能wifi adb实现简介

Android14 串口控制是能wifi adb实现简介 一、前言 文章目录 Android14 串口控制是能wifi adb实现简介一、前言二、Android14 串口控制是能wifi adb实现1、设置prop属性命令开启adb&#xff08;1&#xff09;相关prop属性设置&#xff08;2&#xff09;在设置界面或者 ifconfi…...

vue3中 组合式~测试深入组件:事件 与 $emit()

一、语法(props) 第一步&#xff1a;在组件模板表达式中&#xff0c;可以直接用$emit()方法触发自定义事件&#xff0c; <!-- MyComponent --> <button click"$emit(someEvent)">Click Me</button> 第二步父组件可以通过 v-on (缩写为 ) 来监听…...

SQL-labs13-16闯关记录

http://127.0.0.1/sqli-labs/less-13/ 基于POST单引号双注入变形 1&#xff0c;依然是一个登录框&#xff0c;POST型SQL注入 2&#xff0c;挂上burpsuite&#xff0c;然后抓取请求&#xff0c;构造请求判断漏洞类型和闭合条件 admin 发生了报错&#xff0c;根据提示闭合方式是(…...

基于微信小程序的停车场管理系统的设计与实现

第1章 绪论 1.1 课题背景 随着移动互联形式的不断发展&#xff0c;各行各业都在摸索移动互联对本行业的改变&#xff0c;不断的尝试开发出适合于本行业或者本公司的APP。但是这样一来用户的手机上就需要安装各种软件&#xff0c;但是APP作为一个只为某个公司服务的一个软件&a…...

DAIR-V2X-R数据集服务器下载

【官方github链接】https://github.com/ylwhxht/V2X-R 点击并登录 选择并点击下载 浏览器弹窗&#xff0c;右键选择复制下载链接 ------------------------------------服务器下载----------------------------------------- 登录服务器&#xff0c;选在要下载的文件夹复制路…...

table 拖拽移动

表格拖拽 Sortable.js中文网|配置 <!-- 教务处 --><template><div class"but"><el-button click"mergeAndPrintArrays()" type"primary">保存数据</el-button><el-button click"restoration()" t…...

Linux使用笔记:Find Tree 命令

Tree 命令的使用 使用-I 参数&#xff0c;过滤掉不想展未的目录或文件使用-L参数&#xff0c;指定展示的目录层级个数 arsenaltxzq1899:~/Workspace/vue-application$ tree -I node_modules/ -I public/ -L 2 . ├── components.json ├── Dockerfile ├── ecosystem.c…...

数据结构入门篇——什么是数据结构。

一、引入 工具是一种什么东西呢&#xff1f;是一种转化媒介&#xff0c;我们需要熟食&#xff0c;我们要通过用火来将生肉烤熟。在这个过程中。我们要输入一个东西——生肉&#xff0c;通过工具——火的加工&#xff0c;从而得到我们的目的产物——熟肉。 将上面的例子和红字部…...

MySQL-简介与基本命令

数据库 主流数据库 关系型数据库 MySQL&#xff1a;开源免费的关系型数据库&#xff0c;易于使用和学习&#xff0c;支持大型企业级应用。其特点包括高性能、可靠性和可扩展性&#xff0c;支持多种编程语言和操作系统&#xff0c;拥有大量的社区支持和插件SQLite&#xff1a…...

汽车材料耐候性测试仪器-太阳光模拟器介绍

**太阳光模拟器**是一种用于模拟太阳光谱的设备&#xff0c;广泛应用于汽车材料的耐候性测试。通过模拟太阳光中的紫外线、可见光和红外线&#xff0c;评估材料在长期光照下的性能变化。 主要组成部分 1. **光源系统**&#xff1a; - **氙灯**&#xff1a;最常用的光源&…...

音频3A测试--AEC(回声消除)测试

一、测试前期准备 一台录制电脑:用于作为近段音源和收集远端处理后的数据; 一台测试设备B:用于测试AEC的设备; 一个高保真音响:用于播放设备B的讲话; 一台播放电脑:用于模拟设备A讲话,和模拟设备B讲话; 一台音频处理器(调音台):用于录制和播放数据; 测试使用转接线若…...

DeepSeek 助力 Vue3 开发:打造丝滑的弹性布局(Flexbox)

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;今天给大家分享一篇文章&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到大家或者给大家一些灵感和启发&#xff0c;欢迎收藏关注哦 &#x1f495; 目录 Deep…...

六、Redis 高级功能详解:BitMap、HyperLogLog、Geo、Stream

Redis 高级功能详解:BitMap、HyperLogLog、Geo、Stream Redis 不仅提供了基础的数据结构(String、List、Set、Hash、Sorted Set),还提供了一些高级数据结构,专门用于特定的应用场景,如位运算统计、去重计数、地理位置存储、流数据处理等。本文将详细介绍这些高级功能的使…...

WSL下使用git克隆失败解决

WSL默认nat模式&#xff0c;别动了防火墙放行&#xff0c;见图1git导入[bash1]&#xff0c;ip为你wsl上linxu通过ifconfig获取的本机ip&#xff0c;端口对好某alcsh软件开启tun模式【经过测试&#xff0c;不开也行】应该成了&#xff0c;如果不行&#xff0c;修改.wslconfig为下…...

【Elasticsearch】索引生命周期管理相关的操作(Index Lifecycle Actions)

Elasticsearch 的Index Lifecycle Management(ILM)是一种用于管理索引生命周期的工具&#xff0c;它允许用户根据索引的使用阶段&#xff08;如热、温、冷、冻结&#xff09;自动执行一系列操作。以下是详细解释 Elasticsearch 中的索引生命周期操作&#xff08;Index Lifecycl…...

TS的接口 泛型 自定义类型 在接口中定义一个非必须的属性

TS的接口 泛型 自定义类型 接口 新建一个ts文件&#xff0c;在里面定义一个接口 export interface PersonInter{id:string,name:string,age:number }在vue文件中引入这个ts文件 <script lang"ts" setup name"Person">import {type PersonInter} …...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...