【动态规划-最长公共子序列(LCS)】【hard】【科大讯飞笔试最后一题】力扣115. 不同的子序列
给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数,结果需要对 10^9 + 7 取模。
示例 1:
输入:s = “rabbbit”, t = “rabbit”
输出:3
解释:
如下所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。

示例 2:
输入:s = “babgbag”, t = “bag”
输出:5
解释:
如下所示, 有 5 种可以从 s 中得到 “bag” 的方案。

提示:
1 <= s.length, t.length <= 1000
s 和 t 由英文字母组成
动态规划
class Solution {
public:int numDistinct(string s, string t) {int MOD = 1e9 + 7;int m = s.size(), n = t.size();if(n > m){return 0;}vector<vector<int>> f(m+1, vector<int>(n+1));for(int i = 0; i <= m; i++){f[i][0] = 1;}for(int i = 1; i <= m; i++){for(int j = 1; j <= min(i, n) ; j++){if(s[i-1] == t[j-1]){f[i][j] = (f[i-1][j-1] + f[i-1][j]) % MOD;}else{f[i][j] = f[i-1][j] % MOD;}}}return f[m][n];}
};
时间复杂度:O(mn),其中 m 和 n 分别是字符串 s 和 t 的长度。二维数组 dp 有 m+1 行和 n+1 列,需要对 dp 中的每个元素进行计算。
空间复杂度:O(mn),其中 m 和 n 分别是字符串 s 和 t 的长度。创建了 m+1 行 n+1 列的二维数组 dp。
这个题运用了动态规划的思想,我们首先定义一个二维动态数组f[i][j],设 f[i][j] 表示字符串 s 的前 i 个字符中,子序列中 t 的前 j 个字符出现的次数。
如果 s[i - 1] == t[j - 1],那么 f[i][j] 既可以选择使用 s[i - 1] 来匹配 t[j - 1],也可以不使用 s[i - 1]。此时状态转移方程为:
f[i][j] = (f[i-1][j-1] + f[i-1][j]) % MOD;
如果 s[i - 1] != t[j - 1],则无法匹配 t[j - 1],因此只能继承之前的状态:
f[i][j] = f[i - 1][j]
最后返回f[m][n]。
优化:滚动数组
class Solution {
public:int numDistinct(string s, string t) {int MOD = 1e9 + 7;int m = s.size(), n = t.size();if(n > m){return 0;}vector<int> f(n+1);f[0] = 1;for(int i = 1; i <= m; i++){for(int j = min(i, n); j >= 1 ; j--){if(s[i-1] == t[j-1]){f[j] = (f[j-1] + f[j]) % MOD;}}}return f[n];}
};
我们可以观察到f[i][j] = (f[i-1][j-1] + f[i-1][j]) % MOD;中,f[I][j]上一行的前一个字符转换而来,还有由同一行的前一个字符转换而来。所以我们可以省去行的空间,只定义一个包含列的一维数组f[n],我们在循环中让j倒序,我们就有f[j-1]等同于f[i-1][j-1],f[j]等同于f[i-1][j]。并且在f[i][j] = f[i-1][j] % MOD;中,f[i-1][j]会转换成f[j] = f[j],所以我们不需要列出这种情况。
相关文章:
【动态规划-最长公共子序列(LCS)】【hard】【科大讯飞笔试最后一题】力扣115. 不同的子序列
给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数,结果需要对 10^9 7 取模。 示例 1: 输入:s “rabbbit”, t “rabbit” 输出:3 解释: 如下所示, 有 3 种可以从 s 中得到 “rabbit”…...
深入理解 JavaScript 中的 void`运算符和 yield*表达式
深入理解 JavaScript 中的 void 运算符和 yield* 表达式 在 JavaScript 中,void 运算符和 yield* 表达式是两个功能独特但常被忽视的运算符。本文将详细介绍它们的用法和应用场景,帮助您更好地理解和运用这两个运算符。 目录 void 运算符概述void 运算…...
第四节——从深层剖析指针(让你不再害怕指针)
文章目录 1. 字符指针变量剑指offer例题 2. 数组指针变量2.1 数组指针变量是什么?2.2 数组指针变量怎么初始化 3. ⼆维数组传参的本质代码实现 4. 函数指针变量4.1 函数指针变量的创建4.3 两段有趣的代码4.3.1 typedef 关键字 5. 函数指针数组的定义 1. 字符指针变量…...
openpnp - 吸嘴校正失败的opencv参数分析
文章目录 openpnp - 吸嘴校正失败的opencv参数分析概述笔记阶段验证 - N2吸嘴校验完NT1NT2 阶段验证 - 底部相机高级校验完NT1NT2 参数比对保存 “阶段验证 - N2吸嘴校验完” 的NT1/NT2图像重建参数检测环境NT1ok的3个参数值NT1err的3个参数值NT2ok的3个参数值NT2err的3个参数值…...
【Python】Marmir 使用指南:Python 驱动的电子表格生成器
Marmir 是一个由 Python 驱动的电子表格生成工具,专门用于将 Python 数据结构(如字典、列表等)转换为电子表格文件(如 Excel)。Marmir 的设计目标是提供比传统电子表格库(如 xlwt)更强大和灵活的…...
深入理解 JavaScript 事件循环机制:单线程中的异步处理核心
深入理解 JavaScript 事件循环机制:单线程中的异步处理核心 JavaScript 是一门单线程的编程语言,也就是说它在同一时间只能执行一个任务。然而,现代 Web 应用经常需要处理大量的异步操作,如用户输入、网络请求、定时器等。为了确…...
Stream流的终结方法(二)——collect
1.Stream流的终结方法 2. collect方法 collect方法用于收集流中的数据放到集合中去,可以将流中的数据放到List,Set,Map集合中 2.1 将流中的数据收集到List集合中 package com.njau.d10_my_stream;import java.util.*; import java.util.f…...
【C语言系统编程】【第一部分:操作系统知识】1.1.操作系统原理
第一部分:操作系统知识 1.1 操作系统原理 1.1.1 进程管理 1.1.1.1 进程的概念与生命周期 进程是程序在计算机中的一次执行实例,包括了程序的代码、数据、以及运行的上下文环境。进程管理是操作系统的核心任务之一。 作用:管理所有执行中…...
基于Java+VUE+echarts大数据智能道路交通信息统计分析管理系统
大数据智能交通管理系统是一种基于Web的系统架构,通过浏览器/服务器(B/S)模式实现对城市交通数据的高效管理和智能化处理。该系统旨在通过集成各类交通数据,包括但不限于车辆信息、行驶记录、违章情况等,来提升城市管理…...
leetcode-42. 接雨水 单调栈
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表…...
ThinkPHP和PHP的区别
文章目录 ThinkPHP和PHP的区别一、引言二、PHP简介1、第一步1.1、示例代码 三、ThinkPHP简介2、第二步2.1、特点2.2、示例代码 四、总结 ThinkPHP和PHP的区别 一、引言 在Web开发领域,PHP是一种广泛使用的开源脚本语言,而ThinkPHP则是一个基于PHP的MVC…...
clientWidth,offsetWidth,scrollHeight
clientWidth: offsetWidth: scrollHeight:...
SVN版本回退
SVN 版本回退三种方法: Update item to this version 假设我们的项目文件一共有8个版本,它版本号分别是1,2,3,4,5,6,7,8。 这个选项的作用是将文件版本更新到对应所选的…...
IDEA关联Tomcat
一、Tomcat服务器 web服务器,就是运行web项目的容器 即运行java代码的一个容器 webapp(web应用程序) --> 就是我们写的javaweb项目 Tomcat 是Apache 软件基金会(Apache Software Foundation)下的一个核心项目,免费开源、并支持Servlet 和J…...
MongoDB mongoose 的 save、insert 和 create 方法的比较
目录 save 方法 insert 方法 create 方法 使用会话和事务 总结 在本文中,我们将介绍 MongoDB 中使用 mongoose 操作 数据库时的三种常见方法:save、insert 和 create。这些方法可以用于将数据存储到 MongoDB 数据库中,并且在一定程度上具…...
Maven安装使用
说明:Maven是Apache旗下的一个开源项目,是一款用于管理和构建java项目的工具。一般来说,它帮助我们管理依赖、构建项目。本文介绍在Windows系统下安装Maven。 下载&安装&验证 下载 首先,在Maven官网(https:…...
微信第三方开放平台接入本地消息事件接口报错问题java.security.InvalidKeyException: Illegal key size
先看报错: java.security.InvalidKeyException: Illegal key sizeat javax.crypto.Cipher.checkCryptoPerm(Cipher.java:1039)at javax.crypto.Cipher.implInit(Cipher.java:805)at javax.crypto.Cipher.chooseProvider(Cipher.java:864)at javax.crypto.Cipher.in…...
如何只修改obsidian图片链接为markdown
如何只修改obsidian图片链接为markdown 前言插件配置 使用注意 前言 适合有一定了解obsidian用法和插件市场,还有相对路径的人 插件 在obsidian插件市场搜索—开梯子 配置 首先使用ctrlp打开命令面板,也可以在左侧通过图标打开命令面板,…...
AI不可尽信
看到某项目有类似这样的一段代码 leaves : make([]int, 10) leaves leaves[:0]没理解这样的连续两行,有何作用? 初始化一个长度和容量都为10的切片,接着把切片长度设置为0 即如下demo: (在线地址) package mainimport "fmt"func main() {leaves : make([]int, 1…...
[C++]使用纯opencv部署yolov11旋转框目标检测
【官方框架地址】 GitHub - ultralytics/ultralytics: Ultralytics YOLO11 🚀 【算法介绍】 YOLOv11是一种先进的对象检测算法,它通过单个神经网络实现了快速的物体检测。其中,旋转框检测是YOLOv11的一项重要特性,它可以有效地检…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
