当前位置: 首页 > 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} …...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...