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

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

目录

  • 392.判断子序列
    • 思路
    • 代码
  • 115.不同的子序列
    • 思路
    • 代码

392.判断子序列

Leetcode

在这里插入图片描述

思路

  1. dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]
  2. 递推公式:
    在这里插入图片描述
  3. 初始化:为0
  4. 遍历顺序:从上到下,从左到右
  5. 举例:输入: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

在这里插入图片描述

思路

  1. dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
  2. 递推公式:
    • 当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]
  3. 初始化:从递推公式中看出,左上方和上方是需要初始化的,dp[i][0] 和dp[0][j]是一定要初始化的。dp[i][0] = 1, dp[0][j] = 0, dp[0][0] = 1。
    在这里插入图片描述
    在这里插入图片描述
  4. 遍历顺序:从上到下,从左到右
  5. 举例推导:以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遍历顺序&#xff…...

【国漫逆袭】人气榜,小医仙首次上榜,霍雨浩排名飙升,不良人热度下降

Hello,小伙伴们,我是小郑继续为大家深度解析国漫资讯。 为了提升作品和角色的讨论度,增加平台的用户活跃度,小企鹅推出了动漫角色榜,该榜单以【年】【周】【日】为单位,通过角色的点赞量和互动量进行排名 上周的动漫角…...

国庆中秋特辑(七)Java软件工程师常见20道编程面试题

以下是中高级Java软件工程师常见编程面试题,共有20道。 如何判断一个数组是否为有序数组? 答案:可以通过一次遍历,比较相邻元素的大小。如果发现相邻元素的大小顺序不对,则数组不是有序数组。 public boolean isSort…...

长剖与贪心+树上反悔贪心:1004T4

长剖的本质是一种贪心。(启发式合并本质也是类似哈夫曼树的过程) 在此题中,首先肯定变直径,然后选端点为根。然后选叶子。而每个叶子为了不重复计算,可以只计算其长剖后所在链的贡献。(本题精髓&#xff0…...

二叉树经典例题

前言: 本文主要讲解了关于二叉树的简单经典的例题。 因为二叉树的特性,所以关于二叉树的大部分题目,需要利用分治的思想去递归解决问题。 分治思想: 把大问题化简成小问题(根节点、左子树、右子树)&…...

什么是指针的指针和指向函数的指针?

理解指针的指针和指向函数的指针对于C语言初学者来说可能会有些挑战,但它们都是非常重要的概念,可以帮助你更好地理解和利用C语言的强大功能。在本文中,我将详细解释这两个概念,包括它们的概念、用途和示例。 指针的指针&#xf…...

多个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协议 请求&#xff1a; 应答&#xff1a; ARP协议&#xff1a; 0x0001 0x0800 6 4硬件类型&#xff1a;2个字节&#xff0c;arp协议不仅能在以太网上运行还能在其他类型的硬件上运行。以太网用1来表示&#xff1b; 协议类型&#xff1a;两字节。指的是a…...

【C++】STL详解(十)—— 用红黑树封装map和set

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;C学习 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 上一篇博客&#xff1a;【C】STL…...

Android学习之路(17) Android Adapter详解

Adapter基础讲解 本节引言 从本节开始我们要讲的UI控件都是跟Adapter(适配器)打交道的&#xff0c;了解并学会使用这个Adapter很重要&#xff0c; Adapter是用来帮助填充数据的中间桥梁&#xff0c;简单点说就是&#xff1a;将各种数据以合适的形式显示到view上,提供 给用户看…...

实验室超声波萃取技术的原理和特点是什么?

梵英超声(fanyingsonic)实验室超声波清洗机 超声波萃取中药材的优越性源于超声波的特殊物理性质。通过压电换能器产生的快速机械振动波&#xff0c;超声波可减少目标萃取物与样品基体之间的作用力&#xff0c;从而实现固液萃取分离。 &#xff08;1&#xff09;加速介质质点运…...

用Python操作Word文档,看这一篇就对了!

本文主要讲解Python中操作word的思路。 一、Hello&#xff0c;world&#xff01; 使用win32com需要安装pypiwin32 pip install pypiwin32 推荐使用python的IDLE&#xff0c;交互方便 1、如何新建文档 from win32com.client import Dispatchapp Dispatch(Word.Application…...

力扣 -- 879. 盈利计划(二维费用的背包问题)

解题步骤&#xff1a; 参考代码&#xff1a; 未优化的代码&#xff1a; class Solution { public:int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {//计划数int lengroup.size();//每一维都多开一行空间vector&…...

虚拟机的三种网络连接模式

文章目录 桥接模式NAT模式主机模式 桥接模式 虚拟系统占用主机网段中的一个IP地址&#xff0c;可以正常上网 NAT模式 主机生成一个非本主机的网段的IP的网卡&#xff0c;同时虚拟系统中使用一个该网段的IP地质&#xff0c;网络数据能通过主机的网卡来代理发送出去&#xff0…...

SQL调优

# 插入数据 页合并 # order by优化 视频教程&#xff1a;34. 进阶-SQL优化-order by优化_哔哩哔哩_bilibili 在创建索引的时候&#xff0c;如果没有设置顺序&#xff0c;是会默认升序的&#xff1b;但phone想要倒序&#xff0c;则需要额外的排序 根据需要&#xff0c;创建联合…...

python写一个开机启动的选项

创建一个Python脚本&#xff0c;以便用户可以选择在开机时启动它&#xff0c;可以使用pyautogui库来创建一个简单的交互式界面&#xff0c;其中用户可以选择是否将程序添加到开机启动项中 import pyautogui import osdef add_to_startup():# 提示用户选择是否要在开机时启动程序…...

1500*A. Boredom(DP)

Problem - 455A - Codeforces Boredom - 洛谷 解析&#xff1a; 首先统计每个数的个数&#xff0c;并且统计出最大值mx。 问题转换为&#xff0c;从1-mx 中选择任意个数字&#xff0c;使其都不相邻&#xff0c;求最大的总和。 开始没有思路&#xff0c;以为直接选取偶数位和奇…...

小程序关键词排名:优化你的应用在搜索中的地位

曾经&#xff0c;我们沉浸在应用商店的浩瀚海洋中&#xff0c;寻找着那个能够满足我们需求的小程序。而今&#xff0c;作为开发者&#xff0c;你的小程序究竟能否在这个无边的数字海洋中引起更多涟漪呢&#xff1f;故事的开始&#xff0c;恰巧就在这个问题的探寻中。让我们携手…...

OpenGLES:3D立方体纹理贴图

效果展示 一.概述 前几篇博文讲解了OpenGLES绘制多种3D图形&#xff0c;并赋予丰富的色彩&#xff0c;但是在这些3D图形绘制过程中&#xff0c;有一点还没有涉及&#xff0c;就是纹理贴图。 今天这篇博文我会用如下六张图片对立方体进行纹理贴图&#xff0c;实现六个面都是贴…...

线程的概述

#include <pthread.h> int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg); 功能&#xff1a;创建一个子线程 参数&#xff1a; -thread:传出参数&#xff0c;线程创建成功后&#xff0c;子线程的ID被写到…...

竞赛选题 机器视觉目标检测 - opencv 深度学习

文章目录 0 前言2 目标检测概念3 目标分类、定位、检测示例4 传统目标检测5 两类目标检测算法5.1 相关研究5.1.1 选择性搜索5.1.2 OverFeat 5.2 基于区域提名的方法5.2.1 R-CNN5.2.2 SPP-net5.2.3 Fast R-CNN 5.3 端到端的方法YOLOSSD 6 人体检测结果7 最后 0 前言 &#x1f5…...

python绘图系统27:matplotlib中平面坐标、极坐标和三维坐标的所有绘图函数

文章目录 绘图函数列表为DrawType添加这些绘图函数绘图类别跳转坐标系坐标源代码 绘图函数列表 下面整理了几乎所有matplotlib中的绘图函数&#xff0c;及其在不同坐标轴下的表现。 函数类别2Dpolar3D备注imshow图像X❌❌pcolormesh伪彩图[X,Y,]ZX,Y,Z❌plot曲线图x[,y]x[,y]…...

国庆中秋宅家自省: Python在Excel中绘图尝鲜

【一】国庆中秋: 悟 【国庆中秋】双节来临,相信各位有自己度过的方式,而我却以独特的方式度过了一个说出来不怕各位见笑的双节; 双节到来,没有太多惊喜&#xff0c;也没有太多的负面情绪, 只是喜欢独处,静静反省这些年走过的酸甜苦辣&#xff1b;生活中的许多不欢而散,不期而遇…...

计算机中的进制转换

在计算机软件中&#xff0c;经常需要进行进制转换&#xff0c;这包括二进制、八进制、十进制和十六进制之间的转换。以下是一些常见的转换方法&#xff1a; 二进制转十进制&#xff1a;这是最直接的转换&#xff0c;基本上不需要什么特别的算法。你只需要按照二进制的权值进行…...

Oracle统计信息问题排查常用SQL

Oracle统计信息问题排查常用SQL 对表的基本情况分析统计信息收集作业分析最近一次的统计信息收集修改触发统计信息收集的阈值 对表的基本情况分析 是否为临时表&#xff1a; select owner,table_name,temporary from dba_tables where table_namexxx;是否为分区表&#xff1a…...

css圣杯布局和双飞翼布局

圣杯布局 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice-width, in…...

机器学习笔记 - 深入研究spaCy库及其使用技巧

一、简述 spaCy 是一个用于 Python 中高级自然语言处理的开源库。它专为生产用途而设计,这意味着它不仅功能强大,而且快速高效。spaCy 在学术界和工业界广泛用于各种 NLP 任务,例如标记化、词性标注、命名实体识别等。 安装,这里使用阿里的源。 pip install spacy…...

网站强制跳转至国家反诈中心该怎么办?怎么处理?如何解封?

在互联网环境中&#xff0c;网站安全是非常重要的。然而&#xff0c;在实际操作过程中&#xff0c;不少网站可能因内容问题、技术安全漏洞等原因被迫下线甚至跳转至国家反诈骗中心网址。面对这一严峻问题&#xff0c;我们如何有效解决&#xff0c;让网站恢复运行并解除强制跳转…...