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

【动态规划-最长公共子序列(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 &#xff0c;统计并返回在 s 的 子序列 中 t 出现的个数&#xff0c;结果需要对 10^9 7 取模。 示例 1&#xff1a; 输入&#xff1a;s “rabbbit”, t “rabbit” 输出&#xff1a;3 解释&#xff1a; 如下所示, 有 3 种可以从 s 中得到 “rabbit”…...

深入理解 JavaScript 中的 void`运算符和 yield*表达式

深入理解 JavaScript 中的 void 运算符和 yield* 表达式 在 JavaScript 中&#xff0c;void 运算符和 yield* 表达式是两个功能独特但常被忽视的运算符。本文将详细介绍它们的用法和应用场景&#xff0c;帮助您更好地理解和运用这两个运算符。 目录 void 运算符概述void 运算…...

第四节——从深层剖析指针(让你不再害怕指针)

文章目录 1. 字符指针变量剑指offer例题 2. 数组指针变量2.1 数组指针变量是什么&#xff1f;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 驱动的电子表格生成工具&#xff0c;专门用于将 Python 数据结构&#xff08;如字典、列表等&#xff09;转换为电子表格文件&#xff08;如 Excel&#xff09;。Marmir 的设计目标是提供比传统电子表格库&#xff08;如 xlwt&#xff09;更强大和灵活的…...

深入理解 JavaScript 事件循环机制:单线程中的异步处理核心

深入理解 JavaScript 事件循环机制&#xff1a;单线程中的异步处理核心 JavaScript 是一门单线程的编程语言&#xff0c;也就是说它在同一时间只能执行一个任务。然而&#xff0c;现代 Web 应用经常需要处理大量的异步操作&#xff0c;如用户输入、网络请求、定时器等。为了确…...

Stream流的终结方法(二)——collect

1.Stream流的终结方法 2. collect方法 collect方法用于收集流中的数据放到集合中去&#xff0c;可以将流中的数据放到List&#xff0c;Set&#xff0c;Map集合中 2.1 将流中的数据收集到List集合中 package com.njau.d10_my_stream;import java.util.*; import java.util.f…...

【C语言系统编程】【第一部分:操作系统知识】1.1.操作系统原理

第一部分&#xff1a;操作系统知识 1.1 操作系统原理 1.1.1 进程管理 1.1.1.1 进程的概念与生命周期 进程是程序在计算机中的一次执行实例&#xff0c;包括了程序的代码、数据、以及运行的上下文环境。进程管理是操作系统的核心任务之一。 作用&#xff1a;管理所有执行中…...

基于Java+VUE+echarts大数据智能道路交通信息统计分析管理系统

大数据智能交通管理系统是一种基于Web的系统架构&#xff0c;通过浏览器/服务器&#xff08;B/S&#xff09;模式实现对城市交通数据的高效管理和智能化处理。该系统旨在通过集成各类交通数据&#xff0c;包括但不限于车辆信息、行驶记录、违章情况等&#xff0c;来提升城市管理…...

leetcode-42. 接雨水 单调栈

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [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开发领域&#xff0c;PHP是一种广泛使用的开源脚本语言&#xff0c;而ThinkPHP则是一个基于PHP的MVC…...

clientWidth,offsetWidth,scrollHeight

clientWidth: offsetWidth&#xff1a; scrollHeight&#xff1a;...

SVN版本回退

SVN 版本回退三种方法&#xff1a; Update item to this version 假设我们的项目文件一共有8个版本&#xff0c;它版本号分别是1&#xff0c;2&#xff0c;3&#xff0c;4&#xff0c;5&#xff0c;6&#xff0c;7&#xff0c;8。 这个选项的作用是将文件版本更新到对应所选的…...

IDEA关联Tomcat

一、Tomcat服务器 web服务器,就是运行web项目的容器 即运行java代码的一个容器 webapp(web应用程序) --> 就是我们写的javaweb项目 Tomcat 是Apache 软件基金会&#xff08;Apache Software Foundation&#xff09;下的一个核心项目&#xff0c;免费开源、并支持Servlet 和J…...

MongoDB mongoose 的 save、insert 和 create 方法的比较

目录 save 方法 insert 方法 create 方法 使用会话和事务 总结 在本文中&#xff0c;我们将介绍 MongoDB 中使用 mongoose 操作 数据库时的三种常见方法&#xff1a;save、insert 和 create。这些方法可以用于将数据存储到 MongoDB 数据库中&#xff0c;并且在一定程度上具…...

Maven安装使用

说明&#xff1a;Maven是Apache旗下的一个开源项目&#xff0c;是一款用于管理和构建java项目的工具。一般来说&#xff0c;它帮助我们管理依赖、构建项目。本文介绍在Windows系统下安装Maven。 下载&安装&验证 下载 首先&#xff0c;在Maven官网&#xff08;https:…...

微信第三方开放平台接入本地消息事件接口报错问题java.security.InvalidKeyException: Illegal key size

先看报错&#xff1a; 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用法和插件市场&#xff0c;还有相对路径的人 插件 在obsidian插件市场搜索—开梯子 配置 首先使用ctrlp打开命令面板&#xff0c;也可以在左侧通过图标打开命令面板&#xff0c…...

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 &#x1f680; 【算法介绍】 YOLOv11是一种先进的对象检测算法&#xff0c;它通过单个神经网络实现了快速的物体检测。其中&#xff0c;旋转框检测是YOLOv11的一项重要特性&#xff0c;它可以有效地检…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...