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

别再只盯着Node2vec了!2024年链路预测实战:从传统打分到GNN端到端,一篇搞定

链路预测技术全景&#xff1a;从传统启发式到GNN端到端的实战演进 社交网络的好友推荐、电商平台的"猜你喜欢"、学术论文的引用预测——这些场景背后都依赖链路预测技术。作为图数据挖掘的核心任务之一&#xff0c;链路预测通过分析节点间潜在连接关系&#xff0c;为…...

浏览器资源嗅探终极指南:如何轻松下载网页视频与音频

浏览器资源嗅探终极指南&#xff1a;如何轻松下载网页视频与音频 【免费下载链接】cat-catch 猫抓 浏览器资源嗅探扩展 / cat-catch Browser Resource Sniffing Extension 项目地址: https://gitcode.com/GitHub_Trending/ca/cat-catch 你是否曾想保存网页上的精彩视频却…...

Emmc系列(二)--------协议解析与实战应用

1. Emmc协议基础解析 Emmc协议作为嵌入式存储领域的核心标准&#xff0c;其重要性不言而喻。简单来说&#xff0c;它就像存储设备与主机之间的"普通话"&#xff0c;规定了双方如何高效沟通。我在实际项目中遇到过不少因为协议理解不到位导致的通信故障&#xff0c;今…...

Windows加域必看:如何用PowerShell一键指定OU路径(附完整代码)

Windows域管理自动化&#xff1a;PowerShell指定OU路径的终极指南 在大型企业IT环境中&#xff0c;计算机加域操作从来不是单次事件&#xff0c;而是需要批量执行的常规运维任务。传统手动操作不仅效率低下&#xff0c;还容易因人为失误导致计算机被放入错误的组织单元(OU)。想…...

丹青幻境功能全解析:宣纸UI、动态LoRA、文艺交互实操

丹青幻境功能全解析&#xff1a;宣纸UI、动态LoRA、文艺交互实操 1. 数字艺术创作新范式 在数字艺术创作领域&#xff0c;丹青幻境Z-Image Atelier带来了一场界面革命。这款工具将4090显卡的强大算力隐藏在仿古宣纸界面背后&#xff0c;为创作者提供了前所未有的沉浸式体验。…...

GLM-4.1V-9B-Base保姆级教学:Web界面截图+问题输入框最佳实践

GLM-4.1V-9B-Base保姆级教学&#xff1a;Web界面截图问题输入框最佳实践 1. 认识GLM-4.1V-9B-Base GLM-4.1V-9B-Base是智谱开源的视觉多模态理解模型&#xff0c;专门用于处理图像内容识别、场景描述、目标问答和中文视觉理解任务。这个模型已经完成了Web化封装&#xff0c;可…...

G-Helper终极指南:如何用轻量级工具优化华硕笔记本性能与电池健康

G-Helper终极指南&#xff1a;如何用轻量级工具优化华硕笔记本性能与电池健康 【免费下载链接】g-helper Lightweight, open-source control tool for ASUS laptops and ROG Ally. Manage performance modes, fans, GPU, battery, and RGB lighting across Zephyrus, Flow, TUF…...

嵌入式 - shell 常用语法简单总结

初步使用#!bin/bashecho "Hello world!"echo# shellvim helloworld.shchmod ux helloworld.sh# 在当前bash运行. helloworld.shsource helloworld.sh# 在子bash中运行&#xff0c;无法修改当前shell的变量./helloworld.shLinux中工具链的配置​ ~/.bashrc用于定义当前…...

毕业设计实战:基于SSM+JSP的家纺用品销售管理系统设计与实现全攻略

毕业设计实战&#xff1a;基于SSMJSP的家纺用品销售管理系统设计与实现全攻略 在开发“家纺用品销售管理系统”这套毕设时&#xff0c;我曾因“订单管理与商家库存脱节”踩过一个关键坑。初期设计时&#xff0c;我将“用户下单”和“商家库存扣减”视为两个独立操作&#xff0c…...

用STM32的定时器输入捕获功能,精准解码433MHz遥控器信号(附完整代码)

STM32定时器输入捕获技术解析&#xff1a;433MHz遥控信号精准解码实战 在智能家居DIY和工业控制领域&#xff0c;433MHz无线通信凭借其穿透性强、成本低廉的优势成为常见选择。但如何稳定可靠地解码这些无线信号&#xff0c;一直是开发者面临的挑战。本文将深入探讨基于STM32硬…...