代码随想录算法训练营第五十七天 | 动态规划 part 15 | 392.判断子序列、115.不同的子序列
目录
- 392.判断子序列
- 思路
- 代码
- 115.不同的子序列
- 思路
- 代码
392.判断子序列
Leetcode

思路
dp[i][j]表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]- 递推公式:

- 初始化:为0
- 遍历顺序:从上到下,从左到右
- 举例:输入:s = “abc”, t = “ahbgdc”,dp状态转移图如下:



代码
class Solution:def isSubsequence(self, s: str, t: str) -> bool:dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]for i in range(1, len(s) + 1):for j in range(1, len(t) + 1):if s[i - 1] == t[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = dp[i][j - 1]return dp[-1][-1] == len(s)
- 时间复杂度:
O(n × m) - 空间复杂度:
O(n × m)
115.不同的子序列
Leetcode

思路
dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。- 递推公式:
- 当s[i - 1] 与 t[j - 1]相等时,
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] - 当s[i - 1] 与 t[j - 1]不相等时,dp[i][j]只有一部分组成,不用s[i - 1]来匹配(就是模拟在s中删除这个元素),即:dp[i - 1][j], 所以递推公式为:
dp[i][j] = dp[i - 1][j]
- 当s[i - 1] 与 t[j - 1]相等时,
- 初始化:从递推公式中看出,左上方和上方是需要初始化的,dp[i][0] 和dp[0][j]是一定要初始化的。dp[i][0] = 1, dp[0][j] = 0, dp[0][0] = 1。


- 遍历顺序:从上到下,从左到右
- 举例推导:以s:“baegg”,t:"bag"为例,推导dp数组状态如下:

代码
class Solution:def numDistinct(self, s: str, t: str) -> int:dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]for i in range(len(s) + 1):dp[i][0] = 1for i in range(1, len(s) + 1):for j in range(1, len(t) + 1):if s[i - 1] == t[j - 1]:dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]else:dp[i][j] = dp[i - 1][j]return dp[-1][-1]
- 时间复杂度:
O(n × m) - 空间复杂度:
O(n × m)
相关文章:
代码随想录算法训练营第五十七天 | 动态规划 part 15 | 392.判断子序列、115.不同的子序列
目录 392.判断子序列思路代码 115.不同的子序列思路代码 392.判断子序列 Leetcode 思路 dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]递推公式: 初始化:为0遍历顺序ÿ…...
【国漫逆袭】人气榜,小医仙首次上榜,霍雨浩排名飙升,不良人热度下降
Hello,小伙伴们,我是小郑继续为大家深度解析国漫资讯。 为了提升作品和角色的讨论度,增加平台的用户活跃度,小企鹅推出了动漫角色榜,该榜单以【年】【周】【日】为单位,通过角色的点赞量和互动量进行排名 上周的动漫角…...
国庆中秋特辑(七)Java软件工程师常见20道编程面试题
以下是中高级Java软件工程师常见编程面试题,共有20道。 如何判断一个数组是否为有序数组? 答案:可以通过一次遍历,比较相邻元素的大小。如果发现相邻元素的大小顺序不对,则数组不是有序数组。 public boolean isSort…...
长剖与贪心+树上反悔贪心:1004T4
长剖的本质是一种贪心。(启发式合并本质也是类似哈夫曼树的过程) 在此题中,首先肯定变直径,然后选端点为根。然后选叶子。而每个叶子为了不重复计算,可以只计算其长剖后所在链的贡献。(本题精髓࿰…...
二叉树经典例题
前言: 本文主要讲解了关于二叉树的简单经典的例题。 因为二叉树的特性,所以关于二叉树的大部分题目,需要利用分治的思想去递归解决问题。 分治思想: 把大问题化简成小问题(根节点、左子树、右子树)&…...
什么是指针的指针和指向函数的指针?
理解指针的指针和指向函数的指针对于C语言初学者来说可能会有些挑战,但它们都是非常重要的概念,可以帮助你更好地理解和利用C语言的强大功能。在本文中,我将详细解释这两个概念,包括它们的概念、用途和示例。 指针的指针…...
多个excel合并
目的:将同一个文件下的多个 “京东差评.xlsx” 合并为一个:“京东汇总.xlsx" 代码如下: # -*- coding: utf-8 -*- """ Created on Wed Oct 4 12:52:32 2023author: 64884 """import pandas as pd impor…...
Integrity Plus for Mac,保障网站链接无忧之选
在如今数字化的时代,网站链接的完整性对于用户体验和搜索引擎排名至关重要。如果您是一位网站管理员或者经常需要检查网站链接的人,那么Integrity Plus for Mac(Integrity Plus)将成为您最好的伙伴。 Integrity Plus是一款专业的…...
C#,数值计算——Sobol拟随机序列的计算方法与源程序
1 文本格式 using System; using System.Collections.Generic; namespace Legalsoft.Truffer { /// <summary> /// Sobol quasi-random sequence /// </summary> public class Sobol { public Sobol() { } public static void sobseq(int n,…...
以太网协议介绍(ARP、UDP、ICMP、IP)
以太网协议介绍 一、ARP协议 请求: 应答: ARP协议: 0x0001 0x0800 6 4硬件类型:2个字节,arp协议不仅能在以太网上运行还能在其他类型的硬件上运行。以太网用1来表示; 协议类型:两字节。指的是a…...
【C++】STL详解(十)—— 用红黑树封装map和set
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:C学习 🎯长路漫漫浩浩,万事皆有期待 上一篇博客:【C】STL…...
Android学习之路(17) Android Adapter详解
Adapter基础讲解 本节引言 从本节开始我们要讲的UI控件都是跟Adapter(适配器)打交道的,了解并学会使用这个Adapter很重要, Adapter是用来帮助填充数据的中间桥梁,简单点说就是:将各种数据以合适的形式显示到view上,提供 给用户看…...
实验室超声波萃取技术的原理和特点是什么?
梵英超声(fanyingsonic)实验室超声波清洗机 超声波萃取中药材的优越性源于超声波的特殊物理性质。通过压电换能器产生的快速机械振动波,超声波可减少目标萃取物与样品基体之间的作用力,从而实现固液萃取分离。 (1)加速介质质点运…...
用Python操作Word文档,看这一篇就对了!
本文主要讲解Python中操作word的思路。 一、Hello,world! 使用win32com需要安装pypiwin32 pip install pypiwin32 推荐使用python的IDLE,交互方便 1、如何新建文档 from win32com.client import Dispatchapp Dispatch(Word.Application…...
力扣 -- 879. 盈利计划(二维费用的背包问题)
解题步骤: 参考代码: 未优化的代码: class Solution { public:int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {//计划数int lengroup.size();//每一维都多开一行空间vector&…...
虚拟机的三种网络连接模式
文章目录 桥接模式NAT模式主机模式 桥接模式 虚拟系统占用主机网段中的一个IP地址,可以正常上网 NAT模式 主机生成一个非本主机的网段的IP的网卡,同时虚拟系统中使用一个该网段的IP地质,网络数据能通过主机的网卡来代理发送出去࿰…...
SQL调优
# 插入数据 页合并 # order by优化 视频教程:34. 进阶-SQL优化-order by优化_哔哩哔哩_bilibili 在创建索引的时候,如果没有设置顺序,是会默认升序的;但phone想要倒序,则需要额外的排序 根据需要,创建联合…...
python写一个开机启动的选项
创建一个Python脚本,以便用户可以选择在开机时启动它,可以使用pyautogui库来创建一个简单的交互式界面,其中用户可以选择是否将程序添加到开机启动项中 import pyautogui import osdef add_to_startup():# 提示用户选择是否要在开机时启动程序…...
1500*A. Boredom(DP)
Problem - 455A - Codeforces Boredom - 洛谷 解析: 首先统计每个数的个数,并且统计出最大值mx。 问题转换为,从1-mx 中选择任意个数字,使其都不相邻,求最大的总和。 开始没有思路,以为直接选取偶数位和奇…...
小程序关键词排名:优化你的应用在搜索中的地位
曾经,我们沉浸在应用商店的浩瀚海洋中,寻找着那个能够满足我们需求的小程序。而今,作为开发者,你的小程序究竟能否在这个无边的数字海洋中引起更多涟漪呢?故事的开始,恰巧就在这个问题的探寻中。让我们携手…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
微服务通信安全:深入解析mTLS的原理与实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言:微服务时代的通信安全挑战 随着云原生和微服务架构的普及,服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...
Vue3中的computer和watch
computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...
TJCTF 2025
还以为是天津的。这个比较容易,虽然绕了点弯,可还是把CP AK了,不过我会的别人也会,还是没啥名次。记录一下吧。 Crypto bacon-bits with open(flag.txt) as f: flag f.read().strip() with open(text.txt) as t: text t.read…...
LangChain【6】之输出解析器:结构化LLM响应的关键工具
文章目录 一 LangChain输出解析器概述1.1 什么是输出解析器?1.2 主要功能与工作原理1.3 常用解析器类型 二 主要输出解析器类型2.1 Pydantic/Json输出解析器2.2 结构化输出解析器2.3 列表解析器2.4 日期解析器2.5 Json输出解析器2.6 xml输出解析器 三 高级使用技巧3…...
简单聊下阿里云DNS劫持事件
阿里云域名被DNS劫持事件 事件总结 根据ICANN规则,域名注册商(Verisign)认定aliyuncs.com域名下的部分网站被用于非法活动(如传播恶意软件);顶级域名DNS服务器将aliyuncs.com域名的DNS记录统一解析到shado…...
