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

【算法】动态规划专题④ ——LCS（最长公共子序列）+ LPS（最长回文子序列） python

news 来源：原创 2025/5/11 5:49:08

前置知识

【算法】动态规划专题③ ——二维DP python

子序列定义为：
不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

LCS

最长公共子序列 https://www.lanqiao.cn/problems/1189/learning/?page=1&first_category_id=1&problem_id=1189

题目描述

给定一个长度为N数组a和一个长度为M的数组b。请
你求出它们的最长公共子序列长度为多少。

输入描述
输入第一行包含两个整数N,M,分别表示数组a和b的长度。
第二行包含N个整数a1,a2,…,an。
第三行包含M个整数b1,b2,…,bm

输出描述
输出一行整数表示答案。

1≤N,M≤1e3,1≤ai,bi≤1e9

思路：

定义dp[i][j]表示序列A的前i个元素和序列B的前j个元素之间的最长公共子序列的长度。
当 A[i-1] = B[j-1]，在这种情况下，dp[i][j] = dp[i-1][j-1] + 1
当 A[i-1] != B[j-1]，我们需要决定去掉 A[i]或者B[i]来寻找更大值
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
这里，dp[i-1][j]表示不包括A的第i个元素的最大LCS长度，而dp[i][j-1]表示不包括B的第j个元素的最大LCS长度

代码如下：

n, m = map(int, input().split())
a =list(map(int, input().split()))
b =list(map(int, input().split()))
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):for j in range(1, m + 1):if a[i - 1] == b[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])print(dp[n][m])

通过路径回溯可以重建出具体的LCS

举一反三

两个字符串的删除操作 https://leetcode.cn/problems/delete-operation-for-two-strings/description/

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = “sea”, word2 = “eat”
输出: 2
解释: 第一步将 “sea” 变为 “ea” ，第二步将 "eat "变为 “ea”

示例 2:

输入：word1 = “leetcode”, word2 = “etco”
输出：4

提示：

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

思路：

计算 两个字符串的长度 和 最长公共子序列的长度之差即可

题解code：

class Solution:def minDistance(self, word1: str, word2: str) -> int:n, m = len(word1), len(word2)dp = [[0] * (m + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, m + 1):if word1[i - 1] == word2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return n + m - dp[n][m] * 2

LPS

最长回文子序列 https://leetcode.cn/problems/longest-palindromic-subsequence/description/

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

示例 1：

输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。

示例 2：

输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

思路：

LPS转化为LCS
将s和逆序的s做最长公共子序列即可得到最长回文子序列

code：

class Solution:def longestPalindromeSubseq(self, s: str) -> int:ss = s[::-1]n = len(s)dp = [[0] * (n + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, n + 1):if s[i - 1] == ss[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[n][n]

当然，在此介绍的不是最直接的做法
正规做法属于区间DP，后续会更新

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注谢谢

【算法】动态规划专题④ ——LCS（最长公共子序列）+ LPS（最长回文子序列） python

目录前置知识LCS举一反三LPS 前置知识【算法】动态规划专题③ ——二维DP python 子序列定义为： 不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。 LCS 最长公共子序列 https://www.lanqiao.cn/problems/1189/learning/?p…...

编程日记 2025/5/11 5:49:08

Cesium点集中获取点的id，使用viewer.value.entities.getById报错的解决方法

错误代码： viewer.value.entities.getById(pickedObject.id) 报错： 可以正常获取movement.position但是一直出现如下报错，无法获得航点的id，通过断点定位为 viewer.value.entities.getById(pickedObject.id)导致的报错解决方…...

编程日记 2025/5/10 14:29:58

360手机刷机 360手机解Bootloader 360手机ROOT

360手机刷机 360手机解Bootloader 360手机ROOT 问：360手机已停产，现在和以后，能刷机吗？ 答：360手机，是肯定能刷机的 360手机资源下载网站 360手机-360手机刷机RootTwrp 360os.top 360rom.github.io 一、…...

编程日记 2025/5/11 5:21:58

深度探索DeepSeek-R1：AI大模型的本地应用与个人知识库构建

深度探索DeepSeek-R1：AI大模型的本地应用与个人知识库构建引言在当今这个信息爆炸的时代，如何高效地存储、处理和获取知识，已经成为每个人面临的挑战。想象一下，如果你能在没有互联网连接的情况下，构建一个属于自己…...

编程日记 2025/5/10 17:43:47

LabVIEW图像采集与应变场测量系统

开发了一种基于LabVIEW的图像采集与应变场测量系统，提供一种高精度、非接触式的测量技术，用于监测物体的全场位移和应变。系统整合了实时监控、数据记录和自动对焦等功能，适用于工程应用和科学研究。项目背景传统的位移和应变测量技术往往…...

编程日记 2025/5/6 10:26:01

解决DeepSeek服务器繁忙问题：本地部署与优化方案

deepseek服务器崩了，手把手教你如何在手机端部署一个VIP通道！ 引言随着人工智能技术的快速发展，DeepSeek等大语言模型的应用越来越广泛。然而，许多用户在使用过程中遇到了服务器繁忙、响应缓慢等问题。本文将探讨如何通过本地部…...

编程日记 2025/5/11 4:49:25

今日AI和商界事件(2025-02-05)

今日AI领域的相关事件主要包括以下几个方面： 一、DeepSeek引发全球关注性能与成本优势： DeepSeek推出的R1模型性能出色，成本较低，在全球AI行业引发震动。该模型在数学、代码处理等方面性能优异，受到广泛赞誉。平台…...

编程日记 2025/5/11 4:29:36

SQL 秒变 ER 图 sql转er图

🚀SQL 秒变 ER 图，校园小助手神了！ 学数据库的宝子们集合🙋‍♀️ 是不是每次碰到 SQL 转 ER 图就头皮发麻？看着密密麻麻的代码，脑子直接死机，好不容易理清一点头绪，又被复杂的表关…...

编程日记 2025/5/10 8:15:37

SQL server 创建DB Link 详解

在日常工作中，经常涉及到跨库操作，为使跨数据库的操作变得更加灵活高效，我们可以在 SQL Server 中建立数据库链接（ DB Link），实现 SQL Server 数据库与其他数据库（如 Oracle, MySQL 等&#xff…...

编程日记 2025/5/7 5:23:22

25.2.5学习记录

今天主要学的是哈希表的理论知识，但是都是c实现，C语言的代码实现还没有完全搞明白。在写题的时候，懵懂的学着正确代码，用C语言模拟实现哈希表去解题。在哈希表的理论知识中，学到哈希函数，了解哈希冲突产…...

编程日记 2025/5/11 4:56:21

C# List 列表综合运用实例⁓Hypak原始数据处理编程小结

C# List 列表综合运用实例⁓Hypak原始数据处理编程小结 1、一个数组解决很麻烦引出的问题1.1、RAW 文件尾部数据如下:1.2、自定义标头 ADD 或 DEL 的数据结构如下： 2、程序 C# 源代码的编写和剖析2.1、使用 ref 关键字，通过引用将参数传递，以…...

编程日记 2025/4/30 19:48:25

不可信的搜索路径（CWE-426）

漏洞描述：程序使用关键资源时（如动态链接库、执行文件、配置文件等）没有明确的指定资源的路径，而是依赖操作系统去搜索资源，这种行为可能被攻击者利用，通过在搜索优先级较高的目录放置不良资源，…...

编程日记 2025/5/11 5:28:38

Unity 2D实战小游戏开发跳跳鸟 - 记录显示最高分

上一篇文章中我们实现了游戏的开始界面，在开始界面中有一个最高分数的UI，本文将接着实现记录最高分数以及在开始界面中显示最高分数的功能。添加跳跳鸟死亡事件要记录最高分，则需要在跳跳鸟死亡时去进行判断当前的分数是否是最高分，如果是最高分则进行记录，如果低于之前…...

编程日记 2025/5/11 4:29:36

openeuler 22.03 lts sp4 使用 cri-o 和静态 pod 的方式部署 k8s-v1.32.0 高可用集群

前情提要整篇文章会非常的长…可以选择性阅读，另外，这篇文章是自己学习使用的，用于生产，还请三思和斟酌静态 pod 的部署方式和二进制部署的方式是差不多的，区别在于 master 组件的管理方式是 kubectl 还是 systemctl有 kubeadm 工具，为什么还要用静态 pod 的方式部署？…...

编程日记 2025/5/11 4:10:01

穷举vs暴搜vs深搜vs回溯vs剪枝系列一＞黄金矿工

目录决策树：代码设计代码： 决策树： 代码设计代码： class Solution {boolean[][] vis;int ret,m,n;public int getMaximumGold(int[][] grid) {m grid.length;n grid[0].length;vis new boolean[m][n]; for(int i 0; i <…...

编程日记 2025/5/11 4:23:54

SQL Server配置管理器无法连接到 WMI 提供程序

目录第一步第二部第一步发现没有资源管理器在文件夹找到管理器打开发现报这个错误配置管理器无法连接到 WMI 提供程序第二部 https://blog.csdn.net/thb369208315/article/details/126954074...

编程日记 2025/5/6 21:36:23

微信小程序获取openid和其他接口同时并发请求如何保证先获取到openid

在微信小程序中，如果你需要并发请求获取 openid 和其他接口的数据，并且希望确保先获取到 openid 之后再进行后续操作，可以考虑以下几种方法：方法一：使用 Promise 链 1, 先请求 openid：使用 Promise 来请求 openid。 2, 在获取到 openid 后再请求其他接口。 function g…...

编程日记 2025/5/11 4:28:24

为AI聊天工具添加一个知识系统之87 详细设计之28 Derivation 统一建模元模型之1

文本要点要点 Derivation 统一建模元模型 Derivation 统一建模元模型：意识原型的祖传代码，即支撑程序框架的符号学中的自然和逻辑树。这棵树的雏形中描述了三种建模工件：语用钩子，语法糖和语义胶水。三种工件对应的三“…...

编程日记 2025/5/8 8:43:26

java进阶知识点

java回收机制浅谈java中的反射依赖注入的简单理解通过接口的引用和构造方法的表达，将一些事情整好了反过来传给需要用到的地方~ 这样做得好处：做到了单一职责，并且提高了复用性，解耦了之后，任你如何实现&#xf…...

编程日记 2025/5/7 12:47:05

63.视频推荐的算法|Marscode AI刷题

1.题目问题描述西瓜视频正在开发一个新功能，旨在将访问量达到80百分位数以上的视频展示在首页的推荐列表中。实现一个程序，计算给定数据中的80百分位数。例如：假设有一个包含从1到100的整数数组，80百分位数的值为80&#xf…...

编程日记 2025/5/6 15:04:06

19.[前端开发]Day19-王者荣项目耀实战(二)

01_(掌握)王者荣耀-main-banner展示实现完整代码 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewpor…...

编程日记 2025/5/5 7:03:38

Leetcode面试高频题分类刷题总结

https://zhuanlan.zhihu.com/p/349940945 以下8个门类是面试中最常考的算法与数据结构知识点。排序类（Sort）： 基础知识：快速排序（Quick Sort）， 归并排序（Merge Sort）的…...

编程日记 2025/5/1 23:04:04

JPA使用@EntityGraph立即加载关联实体

在JpaRepository接口中实现自定义查询的时候，必然会遇到一个问题，通过findBy等语句查询出来的结果通常情况下不会加载到关联的实体。例如我有一个Material类，其中有一个属性supplier使用了多对一关联到Supplier类，并开启懒加载&am…...

编程日记 2025/5/7 12:14:40

python多版本管理工具之pyenv

pyenv 是一个用于管理多个 Python 版本的工具，允许用户在同一台机器上轻松安装、切换和隔离不同版本的 Python 解释器。它特别适合需要同时处理多个项目的开发者（例如，不同项目依赖不同 Python 版本的情况）。以下是 pyenv 的详细指南：本文基于Ubuntu 22.04版本进行安装，…...

编程日记 2025/5/10 17:25:04

107，【7】buuctf web [CISCN2019 华北赛区 Day2 Web1]Hack World

这次先不进入靶场看到红框里面的话就想先看看uuid是啥定义与概念 UUID 是 Universally Unique Identifier 的缩写，即通用唯一识别码。它是一种由数字和字母组成的 128 位标识符，在理论上可以保证在全球范围内的唯一性。UUID 的设计目的是让分布式系…...

编程日记 2025/5/7 1:57:12

9. k8s二进制集群之kube-controller-manager部署

同样在部署主机上创建证书请求文件（为之后的证书生成做准备）根据上面的证书文件创建证书（结果会在当前目录下产生kube-controller-manager证书）创建kube-controller-manager服务配置文件创建kube-controller-manager服务启动文件同步kube-controller-manager证书到对应mast…...

编程日记 2025/5/11 0:24:02

keil 单步调试技巧

一、常见错误分析 warningerror警告错误不影响编译过程能够输出Hex文件无法完成编译不输出Hex文件注意的是，warning的信息是要去关注的。下面的UNCALLED SEGMENT除外二、单步调试配置 1、在keil中添加单片机型号本文不详细介绍，如有需要可查看这篇文章：...

编程日记 2025/5/1 23:48:10

[leetcode]两数之和等于target

源代码 #include <iostream> #include <list> #include <iterator> // for std::prev using namespace std; int main() { int target 9; list<int> l{ 2, 3, 4, 6, 8 }; l.sort(); // 确保列表是排序的，因为双指针法要求输入是…...

编程日记 2025/5/6 8:08:33

Go语言的转义字符

文章目录 1. Go语言的转义字符(escapechar)2. 小结和提示 1. Go语言的转义字符(escapechar) 说明:常用的转义字符有如下: \t : 表示一个制表符，通常使用它可以排版\n ：换行符\\ ：一个\\" ：一个"\r ：一个回…...

编程日记 2025/5/1 23:47:38

低代码系统-产品架构案例介绍、蓝凌（十三）

蓝凌低代码系统，依旧是从下到上，从左至右的顺序。技术平台h/iPaas 指低层使用了哪些技术，例如：微服务架构，MySql数据库。个人认为，如果是市场的主流，就没必要赘述了。新一代门户门户设计器&a…...

编程日记 2025/5/7 2:31:59

【大数据技术】搭建完全分布式高可用大数据集群（Hadoop+MapReduce+Yarn）

搭建完全分布式高可用大数据集群（Hadoop+MapReduce+Yarn） jdk-8u361-linux-x64.tarhadoop-3.3.6.tar.gz注：请在阅读本篇文章前，将以上资源下载下来。写在前面本文主要介绍搭建完全分布式高可用集群Hadoop+MapReduce+Yarn的详细步骤。注意：统一约定将软件安装包存放…...

编程日记 2025/5/4 22:51:49

Rapidjson 实战

Rapidjson 是一款 C 的 json 库. 支持处理 json 格式的文档. 其设计风格是头文件库, 包含头文件即可使用, 小巧轻便并且性能强悍. 本文结合样例来介绍 Rapidjson 一些常见的用法. 环境要求有如何的几种方法可以将 Rapidjson 集成到您的项目中. Vcpkg安装: 使用 vcpkg instal…...

编程日记 2025/5/7 21:24:26

string类OJ练习题

目录文章目录前言一、反转字符串二、反转字符串 II 三、反转字符串中的单词 III 四、验证一个字符串是否是回文五、字符串相加（大数加法） 六、字符串相乘（大数乘法） 七、把字符串转化为整数（atoi） 总结…...

编程日记 2025/5/11 1:26:06

Python进行模型优化与调参

在数据科学与机器学习领域，模型的优化与调参是提高模型性能的重要步骤之一。模型优化可以帮助提高模型的准确性和泛化能力，而合理的调参则能够充分发挥模型的潜力。这篇教程将重点介绍几种常用的模型优化与调参方法，特别是超参数调整和正则化技术的应用。这些技术能够有效地…...

编程日记 2025/5/9 21:15:59

Ollama+deepseek+Docker+Open WebUI实现与AI聊天

1、下载并安装Ollama 官方网址：Ollama 安装好后，在命令行输入， ollama --version 返回以下信息，则表明安装成功， 2、下载AI大模型这里以deepseek-r1:1.5b模型为例， 在命令行中，执行&…...

编程日记 2025/5/1 3:39:23

【PDF多区域识别】如何批量PDF指定多个区域识别改名，基于Windows自带的UWP的文字识别实现方案

海关在对进口货物进行查验时，需要核对报关单上的各项信息。对报关单 PDF 批量指定区域识别改名后，海关工作人员可以更高效地从文件名中获取关键信息，如货物来源地、申报价值等。例如文件名 “[原产国]_[申报价值].pdf”，有助于海关快速筛选重点查验对象，提高查验效率和监管…...

编程日记 2025/5/6 23:44:52

第一个Qt开发实例(一个Push Button按钮和两个Label)【包括如何在QtCreator中创建新工程、代码详解、编译、环境变量配置、测试程序运行等】

目录 Qt开发环境QtCreator的安装、配置在QtCreator中创建新工程在Forms→mainwindow.ui中拖曳出我们要的图形按钮查看拖曳出按钮后的代码为pushButton这个图形添加回调函数编译工程关闭开发板上QT的GUI(选做)禁止LCD黑屏(选做)设置Qt运行的环境变量运行Qt程序如何让程序在系统启…...

编程日记 2025/5/4 17:32:42

算法题（58）：盛水最多的容器

审题： 需要我们找到数组height中的数据构建的可以盛水最多的容器，并把容量返回思路： 容量最短的容器边界 * 容器宽度方法一：双层for循环我们可以把所有情况枚举出来，然后维护一个最大容量方法二：双指…...

编程日记 2025/5/8 15:50:35

MyBatis持久层框架

第1章 Mybatis框架入门 1.1 Mybatis简介 MyBatis最初是Apache的一个开源项目iBatis, 2010年6月这个项目由Apache Software Foundation迁移到了Google Code。随着开发团队转投Google Code旗下， iBatis3.x正式更名为MyBatis。代码于2013年11月迁移到Github。 MyBati…...

编程日记 2025/5/6 12:30:34

DeePseek结合PS！批量处理图片的方法教程

今天我们来聊聊如何利用deepseek和Photoshop（PS）实现图片的批量处理。传统上，批量修改图片尺寸、分辨率等任务往往需要编写脚本或手动处理，而现在有了AI的辅助，我们可以轻松生成PS脚本，实现自动化处…...

编程日记 2025/5/10 3:07:00

【C++】多态（下）

大家好，我是苏貝，本篇博客带大家了解C的多态，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️ 目录 4. 多态的原理4.1 虚函数表4.2 多态的原理4.3 动态绑定与静态绑定 5. 单继承和多继承关系的虚…...

编程日记 2025/5/8 14:30:16

C++ 入门速通-第4章【黑马】

内容来源于：黑马集成开发环境：CLion 先前学习完了C第1章的内容： C 入门速通-第1章【黑马】-CSDN博客 C 入门速通-第2章【黑马】-CSDN博客 C 入门速通-第3章【黑马】-CSDN博客下面继续学习第4章： 结构体的基本应用&#xff1…...

编程日记 2025/5/7 23:32:23

Gauss高斯:分布键

分布键是决定数据分布到不同节点的列，直接影响数据的存储位置和后续查询的数据流向. 在分布式数据库系统中，分布键用于决定数据如何在不同的节点或分区中分布。作用分类分布键的选择避免常量过滤条件的字段：在选择分布键时，…...

编程日记 2025/5/10 22:02:44

Spring Security(maven项目) 3.0.3.1版本 - 动态JDBC认证

前言： 通过实践而发现真理，又通过实践而证实真理和发展真理。从感性认识而能动地发展到理性认识，又从理性认识而能动地指导革命实践，改造主观世界和客观世界。实践、认识、再实践、再认识，这种形式，循环往…...

编程日记 2025/5/10 2:51:42

2024年半导体行业IPO与融资情况统计分析

重点内容速览： 1. IPO企业主要集中在科创板 2. 全年半导体行业融资事件超700起 2024年半导体行业的IPO和融资情况呈现出了显著的波动和变化。由于IPO政策的收紧，2024年成功上市的企业相比2023年的22家和2022年的45家有了显著降低，今年仅有1…...

编程日记 2025/5/5 7:36:15

Java 进阶 01 —— 5 分钟回顾一下 Java 基础知识

Java 进阶 01 —— 5 分钟回顾一下 Java 基础知识 Java 生态圈Java 跨平台的语言 Java 虚拟机规范JVM 跨语言的平台多语言混合编程两种架构举例 JVM 的生命周期虚拟机的启动虚拟机的执行虚拟机的退出 JVM 发展历程 Sun Classic VMExact VMHotSpotBEA 的 JRockitIBM 的 J9 …...

编程日记 2025/4/30 21:08:46