当前位置: 首页 > 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;它可以有效地检…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具&#xff0c;专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑&#xff08;如DBC、LDF、ARXML、HEX等&#xff09;&#xff0c;并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...