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

动态规划入门:爬楼梯与打家劫舍问题解析

发布时间:2026/11/19 19:53:18 来源:云帆数科 栏目:资讯中心
动态规划入门:爬楼梯与打家劫舍问题解析
1. 动态规划入门从爬楼梯到打家劫舍LeetCode上的动态规划问题总是让人又爱又恨——看似简单的题目背后往往隐藏着精妙的解题思路。今天我们就来拆解两个经典题目70.爬楼梯和198.打家劫舍。这两个问题看似毫不相关实则都体现了动态规划的核心思想。我第一次接触爬楼梯问题时直觉反应是用递归解决。但当输入n45时递归解法直接超时这才意识到问题的复杂性。而打家劫舍问题更是让我栽了跟头——最初尝试用贪心算法结果发现根本无法覆盖所有情况。经过反复尝试和思考终于理解了这两个问题背后的动态规划本质。2. 爬楼梯问题解析2.1 问题描述与初步思考爬楼梯问题的描述很简单假设你正在爬楼梯需要n阶才能到达楼顶。每次你可以爬1或2个台阶。问有多少种不同的方法可以爬到楼顶例如n2时有2种方法11或直接2n3时有3种方法111、12、21看到这个问题我的第一反应是递归。因为爬到第n阶楼梯要么是从n-1阶跨1步上来要么是从n-2阶跨2步上来。所以递推公式似乎是f(n)f(n-1)f(n-2)。2.2 递归解法及其缺陷基于上述思路我很快写出了递归解法def climbStairs(n): if n 1: return 1 if n 2: return 2 return climbStairs(n-1) climbStairs(n-2)这个解法在小规模输入时工作正常但当n45时运行时间变得不可接受。原因在于递归过程中存在大量重复计算时间复杂度达到了O(2^n)。2.3 动态规划解法优化为了优化性能我改用动态规划方法使用一个数组来存储中间结果def climbStairs(n): if n 1: return 1 dp [0]*(n1) dp[1] 1 dp[2] 2 for i in range(3, n1): dp[i] dp[i-1] dp[i-2] return dp[n]这种方法将时间复杂度降到了O(n)空间复杂度也是O(n)。但进一步观察发现我们其实只需要前两个状态因此可以继续优化空间def climbStairs(n): if n 1: return 1 first, second 1, 2 for _ in range(3, n1): first, second second, first second return second这样空间复杂度降到了O(1)这是最优解法。3. 打家劫舍问题解析3.1 问题描述与难点打家劫舍问题描述为你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你的唯一制约因素是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报的情况下能够偷窃到的最高金额。例如输入[1,2,3,1]输出4解释偷窃第1号和第3号房屋(134)这个问题比爬楼梯复杂因为需要考虑更多条件。我最初尝试用贪心算法每次都选择当前能偷的最大值但很快就发现这种策略无法保证全局最优。3.2 动态规划状态定义经过反复思考我意识到这也是一道动态规划问题。关键在于如何定义状态和状态转移方程。定义dp[i]为偷到第i间房屋时能获得的最大金额。对于第i间房屋有两种选择偷它那么不能偷i-1最大金额是dp[i-2]nums[i]不偷它最大金额保持dp[i-1]因此状态转移方程为 dp[i] max(dp[i-1], dp[i-2]nums[i])3.3 完整解法实现基于这个思路我写出了以下解法def rob(nums): if not nums: return 0 if len(nums) 1: return nums[0] dp [0]*len(nums) dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, len(nums)): dp[i] max(dp[i-1], dp[i-2]nums[i]) return dp[-1]同样地我们可以优化空间复杂度def rob(nums): prev_max curr_max 0 for num in nums: temp curr_max curr_max max(curr_max, prev_max num) prev_max temp return curr_max这种解法时间复杂度O(n)空间复杂度O(1)非常高效。4. 两问题的联系与动态规划思想4.1 问题共性分析爬楼梯和打家劫舍看似不同实则都体现了动态规划的核心特征最优子结构问题的最优解包含子问题的最优解重叠子问题算法会反复计算相同的子问题无后效性当前状态只与前面有限个状态有关4.2 动态规划解题框架通过这两个问题我总结出了动态规划解题的一般步骤定义状态明确dp[i]代表什么含义确定状态转移方程找出dp[i]与前面状态的关系初始化确定初始状态的值考虑边界条件选择计算顺序通常是自底向上空间优化如果可能4.3 常见错误与调试技巧在实际编码中我遇到过几个典型错误边界条件处理不当比如n0或nums为空数组的情况数组越界特别是在处理dp[i-2]时忘记检查i2初始状态设置错误比如dp[1]应该取max(nums[0],nums[1])而非nums[1]调试时我通常会先用小例子手动计算预期结果打印中间状态数组检查是否符合预期特别注意循环的起始和终止条件5. 进阶思考与变种问题5.1 爬楼梯变种原问题中每次只能爬1或2阶如果改为可以爬1、2或3阶呢状态转移方程变为 f(n) f(n-1) f(n-2) f(n-3)如果每次能爬的台阶数是一个数组steps中的任意值则def climbStairsVariation(n, steps): dp [0]*(n1) dp[0] 1 for i in range(1, n1): for step in steps: if i step: dp[i] dp[i-step] return dp[n]5.2 打家劫舍变种LeetCode上还有打家劫舍II房屋围成一圈和打家劫舍III房屋排列成二叉树的变种。以打家劫舍II为例关键思路是将环形问题拆解为两个线性问题不偷第一间房屋不偷最后一间房屋然后取两种情况的最大值def robII(nums): if len(nums) 1: return nums[0] return max(rob(nums[:-1]), rob(nums[1:]))5.3 其他类似问题掌握了这两个问题的解法后我发现很多问题都有相似的模式最小花费爬楼梯每一步有成本求最小总成本最长递增子序列定义dp[i]为以nums[i]结尾的最长子序列长度最大子数组和Kadane算法的动态规划版本6. 实战经验与性能优化6.1 测试用例设计为了确保代码正确性我通常会设计以下几类测试用例最小输入n0或nums[]小规模输入手动可验证的简单情况边界情况如n1或nums长度刚好为2大规模输入测试性能6.2 时间与空间复杂度分析对于动态规划问题通常时间复杂度O(n)因为需要遍历所有状态空间复杂度基础版本O(n)优化后O(1)当遇到更复杂的状态定义时如二维dp复杂度会相应增加。6.3 实际编码技巧在实现过程中我总结了一些实用技巧使用注释明确每个状态的定义先写出基础版本确保正确后再优化空间对于Python可以用元组同时更新多个变量避免临时变量在循环开始时处理边界条件使主逻辑更清晰7. 学习资源与练习建议7.1 推荐学习路径对于想系统学习动态规划的同学我建议的学习顺序是斐波那契数列 → 爬楼梯 → 打家劫舍背包问题系列01背包、完全背包字符串相关DP最长公共子序列、编辑距离更复杂的二维DP问题7.2 经典题目清单以下是我认为必做的动态规划题目爬楼梯打家劫舍最大子数组和零钱兑换最长递增子序列最长公共子序列7.3 刷题策略建议根据我的经验有效的刷题策略是先独立思考至少尝试30分钟如果卡住看提示而非完整解答理解解法后自己重新实现24小时后再次尝试同一题目总结相似题目的解题模式8. 从理论到实践的思考动态规划之所以难是因为它需要我们将问题分解并找到合适的状态定义。经过大量练习后我开始能够识别问题的DP特征计数问题如爬楼梯的方法数最值问题如最大金额、最小成本存在性判断如能否分割等和子集在实际工程中动态规划思想也有广泛应用比如文本差异比较资源分配优化路径规划问题我个人的体会是动态规划的学习曲线虽然陡峭但一旦掌握了核心思想很多难题都会迎刃而解。建议从简单题目入手逐步建立信心不要一开始就挑战最难的题目。

相关推荐

提示工程架构师:AI交互设计的核心挑战与优化策略
提示工程架构师:AI交互设计的核心挑战与优化策略

1. 提示工程架构师的角色定位与核心挑战当AI系统开始接管越来越多的交互场景时,一个新兴职业正在悄然崛起——提示工程架构师(Prompt Engineering Architect)。这个角色不同于传统的AI工程师或产品经理,他们更像是"人机对话的… · 2026/11/19 19:53:16

JMeter安装与配置全指南:从Java环境到性能测试
JMeter安装与配置全指南:从Java环境到性能测试

1. JMeter安装前的准备工作在开始安装JMeter之前,我们需要做好几项准备工作。首先确认你的操作系统版本,JMeter支持Windows、Linux和macOS三大主流平台。我建议使用Windows 10/11或macOS 10.15及以上版本,这些系统对JMeter的兼容性最好。重要… · 2026/11/19 19:53:17

VB.NET OPC DA 客户端示例:COM互操作、异步订阅与断线重连
VB.NET OPC DA 客户端示例:COM互操作、异步订阅与断线重连

简介:面向VB.NET开发者与工业自动化入门者的OPC通信基础示例,围绕在VB.NET项目中接入OPC服务器这一常见需求展开,适合作为教学演示和二次开发的起点。压缩包共38个文件,约194KB,包含4个vb源代码文件、2个vbproj项目文件… · 2026/11/17 18:32:42

物业电工作业时间千万别踩坑,学历不高也能报名
物业电工作业时间千万别踩坑,学历不高也能报名

物业电工作业时间千万别踩坑,学历不高也能报名 你是不是也担心自己学历不高,怕报不了名?别慌, 物业电工作业时间 其实对学历要求并不高,关键是要选对培训机构。很多同学在报名前就踩过坑,结果钱花了,证没拿到,白白浪费时间和精力。这篇文章就带你避… · 2026/11/19 19:52:45

镇江大港电工证考试怎么考?官方报名入口在哪?上岗找工作必看!
镇江大港电工证考试怎么考?官方报名入口在哪?上岗找工作必看!

镇江大港电工证考试怎么考?官方报名入口在哪?上岗找工作必看! 你是不是也正为找工作发愁? 急需特种作业证才能上岗找工作 ,这已经是很多从业者的真实写照。尤其是像 镇江大港电工证考试… · 2026/11/19 19:52:45

山西特种工复审题库良心建议:别再被中介坑了,自己掌握考试重点
山西特种工复审题库良心建议:别再被中介坑了,自己掌握考试重点

山西特种工复审题库良心建议:别再被中介坑了,自己掌握考试重点 你是不是也在为山西特种工复审题库发愁?怕被中介坑、不知道去哪里报名、不知道考试内容?别慌,这波【山西特种工复审题库良心建议】来了,让你轻松应对复审,避免踩坑。… · 2026/11/19 19:52:45

电工证漏审怎么考?保姆级教程教你一步步补救
电工证漏审怎么考?保姆级教程教你一步步补救

电工证漏审怎么考?保姆级教程教你一步步补救 之前考的证在外省能不能转过来?别急,今天就给你来个保姆级教程,教你怎么处理电工证漏审问题,别让一张证毁了你的职业前途。 电工证漏审是什么?有什么后果? 漏审 ,简单来说就是你拿到电工证之后,… · 2026/11/19 19:52:45

电工证复审费报销吗 2026河南最新政策全知道
电工证复审费报销吗 2026河南最新政策全知道

电工证复审费报销吗 2026河南最新政策全知道 怕考不过白交培训费?别慌!2026河南最新政策已经明确,电工证复审费 是可以报销的… · 2026/11/19 19:52:45

电工证丢了怎么补办?电工作业安全反思书+通过率揭秘全攻略
电工证丢了怎么补办?电工作业安全反思书+通过率揭秘全攻略

电工证丢了怎么补办?电工作业安全反思书+通过率揭秘全攻略 你是不是也在为电工证丢了不知道去哪补办发愁?怕被中介坑、怕流程复杂、怕耽误工作?别急,今天咱们就从头到尾说说电工作业安全反思书的相关问题,还带你看清 通过率揭秘… · 2026/11/19 19:51:45

长春初级电工证怎么考?通过率揭秘全在这里
长春初级电工证怎么考?通过率揭秘全在这里

长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/19 16:06:02

国内电工证报考条件与考试时间
国内电工证报考条件与考试时间

低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/19 17:40:37

电工作业时如何断电?电子证书到底能不能全国通用?
电工作业时如何断电?电子证书到底能不能全国通用?

电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/19 17:50:07

姑苏区哪里考电工证好考前押题怎么找
姑苏区哪里考电工证好考前押题怎么找

姑苏区哪里考电工证好考前押题怎么找 工地太忙根本没时间复习考试,电工证考前还总找不到靠谱的 考前押题 资源,真让人头疼。如果你也是在苏州姑苏区从事建筑或电力行业的,那这些建议你一定要看完。 为什么姑苏区考电工证的人这么多?… · 2026/11/19 0:00:12

罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南
罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南

罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南 之前考的证在外省能不能转过来?这几乎是每个特种作业证书持有者都会遇到的问题,特别是像你这样已经在外地工作多年,想回老家罗定发展或者重新规划职业路径的人。别急,今天就给你一条清晰的路… · 2026/11/19 0:00:12

罗定能考电工证吗 电工证含金量到底有多少?
罗定能考电工证吗 电工证含金量到底有多少?

罗定能考电工证吗 电工证含金量到底有多少? 之前考的证在外省能不能转过来,这几乎是每个准备考电工证的朋友最先想到的问题。特别是在罗定这样的地方,很多人的电工证都是在外地考的,现在想在当地继续使用,但不知道怎么办。实际上,电工证的 含金量… · 2026/11/19 0:00:12

双极步进电机控制实战: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/19 6:33:25

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/19 6:33:32

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/19 0:22:38

了解更多?预约专属演示

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

企业微信二维码