首页/新闻资讯/正文详情

动态规划入门:最长上升子序列问题解析

发布时间:2026/11/5 14:53:15 来源:云帆数科 栏目:资讯中心
动态规划入门:最长上升子序列问题解析
1. 动态规划入门从最长上升子序列说起动态规划Dynamic Programming简称DP是算法设计中一种非常重要的思想它通过将复杂问题分解为更小的子问题来解决。我第一次接触动态规划时被它的精妙所震撼但同时也被它的抽象性所困扰。今天我们就以最长上升子序列Longest Increasing SubsequenceLIS问题为例来揭开动态规划的神秘面纱。最长上升子序列问题描述很简单给定一个无序的整数数组找到其中最长的严格递增子序列的长度。例如对于数组[10,9,2,5,3,7,101,18]最长的上升子序列是[2,3,7,101]长度为4。2. 暴力解法与问题分析2.1 暴力搜索的局限性最直观的解法是枚举所有可能的子序列然后检查它们是否是上升的。对于一个长度为n的数组它有2^n个子序列每个元素可以选择包含或不包含检查每个子序列是否上升需要O(n)时间因此总时间复杂度是O(n*2^n)。这在n20时就已经需要处理约2000万种可能性显然不适用于实际问题。2.2 寻找最优子结构动态规划的核心思想是问题具有最优子结构性质一个问题的最优解包含其子问题的最优解。对于LIS问题我们可以观察到以nums[i]结尾的LIS长度取决于所有j i且nums[j] nums[i]的情况我们需要在这些情况中选择能形成最长序列的那个这种性质提示我们可以使用动态规划来解决这个问题。3. 动态规划解法详解3.1 定义状态我们定义dp[i]为以第i个数字结尾的最长上升子序列的长度。注意这个定义非常关键它决定了我们如何构建状态转移方程。例如对于数组nums [10,9,2,5,3,7,101,18]dp[2] 1以2结尾的LIS就是[2]dp[3] 2以5结尾的LIS可以是[2,5]dp[4] 2以3结尾的LIS可以是[2,3]3.2 状态转移方程对于每个i我们需要检查所有j i如果nums[j] nums[i]那么nums[i]可以接在nums[j]后面形成更长的子序列我们选择能形成最长子序列的那个j因此状态转移方程为 dp[i] max(dp[j] 1) 对所有j i且nums[j] nums[i]如果不存在这样的j则dp[i] 1子序列只包含nums[i]本身3.3 基础实现def lengthOfLIS(nums): if not nums: return 0 dp [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)这个实现的时间复杂度是O(n^2)空间复杂度是O(n)。对于n2500如LeetCode上的约束这个解法是完全可行的。4. 优化解法贪心二分查找4.1 直觉与思路虽然O(n^2)的解法已经不错但我们可以做得更好。观察到一个关键性质在相同长度的情况下我们希望子序列的最后一个数尽可能小这样后面有更多机会接上更大的数。这提示我们可以维护一个数组tails其中tails[i]表示长度为i1的所有上升子序列中结尾最小的那个数字。4.2 算法步骤初始化tails数组为空对于每个数字num如果num大于tails的所有元素则将其添加到tails末尾否则用num替换tails中第一个大于等于它的元素最终tails的长度就是LIS的长度这个替换操作可以用二分查找来高效实现。4.3 优化实现def lengthOfLIS(nums): tails [] for num in nums: # 二分查找第一个大于等于num的元素 left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid if left len(tails): tails.append(num) else: tails[left] num return len(tails)这个算法的时间复杂度是O(n log n)因为对于每个元素我们进行一次O(log n)的二分查找操作。5. 实际应用与变种5.1 俄罗斯套娃信封问题这是一个经典的二维LIS问题。给定一些信封的宽度和高度如果一个信封的宽度和高度都比另一个大就可以套进去。问最多能套多少层。解法先对宽度升序排序宽度相同的按高度降序排序然后在高度序列上找LISdef maxEnvelopes(envelopes): envelopes.sort(keylambda x: (x[0], -x[1])) heights [h for _, h in envelopes] return lengthOfLIS(heights)5.2 其他变种最长不下降子序列允许相等带权值的LIS求最大权值和而非最长长度需要输出具体的LIS而不仅仅是长度6. 动态规划的思考框架通过LIS问题我们可以总结出解决动态规划问题的一般步骤定义状态明确dp数组的含义确定初始条件base case建立状态转移方程确定计算顺序考虑优化空间如滚动数组对于LIS问题我们经历了从暴力解法到标准DP再到优化解法的过程。在实际编程面试中理解并能够实现O(n log n)的解法会给你带来很大优势。7. 常见错误与调试技巧在实现LIS算法时容易犯的几个错误错误的状态定义比如定义dp[i]为前i个元素的LIS长度这样难以建立状态转移忽略初始条件每个dp[i]至少为1二分查找实现错误注意边界条件和等号处理调试时可以打印dp数组观察变化对小例子手动计算验证特别注意边界情况空数组、单元素数组、完全逆序数组等8. 扩展练习为了巩固对LIS和动态规划的理解建议尝试以下LeetCode题目最长上升子序列基础俄罗斯套娃信封问题二维最长递增子序列的个数统计数量最长数对链变种记住掌握动态规划的关键在于多练习、多思考状态的定义和转移。LIS问题作为一个经典例题理解它对于掌握动态规划至关重要。

相关推荐

NSGA-II与Maxwell集成的电机多目标优化实践
NSGA-II与Maxwell集成的电机多目标优化实践

1. 项目背景与核心挑战在电机设计领域,工程师们常常面临一个经典难题:如何同时优化多个相互冲突的性能指标?以永磁同步电机为例,平均转矩、转矩脉动和齿槽转矩这三个关键参数往往此消彼长。传统的手动试错法不仅效率低下&#xff… · 2026/11/4 1:10:14

运维工程师职业发展:技术之外的四大核心能力
运维工程师职业发展:技术之外的四大核心能力

1. 运维职业发展的核心矛盾在技术行业摸爬滚打十几年,我发现一个有趣的现象:那些晋升最快的运维工程师,往往不是技术最顶尖的。这个现象背后隐藏着运维岗位的特殊性——技术能力只是职业发展的基础要素,而非决定性因素。运维工作的… · 2026/11/3 13:00:33

JPG格式转换全解析:有损压缩、透明通道与批量处理避坑
JPG格式转换全解析:有损压缩、透明通道与批量处理避坑

1. 先把"转换"这个词拆开:JPG到底在转什么问"图片jpg格式怎么转换"的人,十有八九不是真的想知道JPEG的编码原理,而是手上正卡着某件具体的事:一张图传不上去、一个文件夹里格式乱七八糟、一张PNG拖进某个系统… · 2026/11/3 2:29:02

ADS122U04IPWR+STM32F427ZI工业级温度测量信号链设计
ADS122U04IPWR+STM32F427ZI工业级温度测量信号链设计

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 14:10:41

UART接口24位ADC搭配RS485,解决远距离温度监控难题
UART接口24位ADC搭配RS485,解决远距离温度监控难题

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 14:10:41

UART接口24位ADC搭配PIC18F46K22的RTD与热电偶测温实践
UART接口24位ADC搭配PIC18F46K22的RTD与热电偶测温实践

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 14:10:41

GD32E10x官方例程入门:从GPIO点灯到串口调试
GD32E10x官方例程入门:从GPIO点灯到串口调试

简介:这份GD32E10x系列官方例程面向嵌入式硬件与单片机开发者,基于ARM Cortex-M3内核,汇集兆易创新GD32E10x的示例代码,适合工业控制、消费电子、通信设备等场景的学习、验证与二次开发。压缩包共935个文件,约11.16MB&… · 2026/11/5 13:52:29

基于Django的运维平台实战:资产、发布、巡检、告警一体化
基于Django的运维平台实战:资产、发布、巡检、告警一体化

简介:这份资源是一套基于Django框架开发的运维平台源码,面向具备Python基础、希望了解Web运维系统实现思路的开发者与运维人员,可用于学习主机管理、服务监控、日志查看、任务调度、权限控制、资源统计、脚本执行与故障告警等常见运维模块的落… · 2026/11/5 13:49:27

基于ADS122U04IPWR与STM32F427ZI的工业测温方案设计
基于ADS122U04IPWR与STM32F427ZI的工业测温方案设计

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 13:22:54

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:27:59

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:03

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:07

多智能体协作系统架构设计与实践优化
多智能体协作系统架构设计与实践优化

1. 多智能体协作系统的时代背景2017年Transformer架构的诞生彻底改变了人工智能的发展轨迹。当行业还沉浸在单一大模型带来的性能突破时,Anthropic的研究团队已经将目光投向了更前沿的领域——如何让多个智能体通过协作产生超越单体能力的系统智能。这就像交响乐团中… · 2026/11/5 0:00:39

大模型系统性入门实战指南:从原理到部署微调的全链路路线
大模型系统性入门实战指南:从原理到部署微调的全链路路线

提到大模型的系统性入门,我先说个结论:这事真不难,难的是资料太散、路线太多,今天这个框架明天那个工具,新人很容易在“收藏夹吃灰”和“教程看到一半放弃”之间反复横跳。市面上关于大模型的内容少说有几十万篇&#… · 2026/11/5 0:00:39

鸿蒙文件系统沙箱机制解析与开发实践
鸿蒙文件系统沙箱机制解析与开发实践

1. 鸿蒙文件系统沙箱机制深度解析作为一名从Android转向鸿蒙开发的工程师,我深刻体会到文件系统访问是迁移过程中最先遇到的"拦路虎"。在Android上运行良好的文件读写代码,在鸿蒙真机环境却频频出现文件写入后神秘消失或直接抛出权限拒绝错误的… · 2026/11/5 0:00:39

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:27:59

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:03

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:07

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码