前言动态规划这块我从一开始看到题目就懵到现在能独立写出三道经典题中间踩了不少坑。这篇文章把我真实的思考过程和犯错记录写下来希望能帮到和我一样刚开始接触DP的同学。第一步爬楼梯 —— 理解“最后一步分类”题目每次可以爬1级或2级台阶爬到第n级有多少种不同的方法我的理解过程一开始我看到递推公式dp[i] dp[i-1] dp[i-2]完全不知道是怎么来的。后来老师用“最后一步”的思路帮我拆解要走到第i级台阶最后一步要么是从第i-1级跨1步上来要么是从第i-2级跨2步上来所以走到第i级的方法数 走到第i-1级的方法数 走到第i-2级的方法数这个“最后一步分类”的思路是DP的核心思想之一站在终点往前看把问题拆成几种可能性。滚动变量的优化基础版本用数组存储所有状态空间复杂度O(n)。优化后只用三个变量滚动def climbStairs(n): if n 2: return n a, b 1, 2 for i in range(3, n 1): c a b a, b b, c return b老师当时打了个比方就像滚雪球a和b不断往前滚旧的数字就被丢掉了。这个比喻让我一下就记住了。关键领悟DP的本质是反向思考、正向计算。我们从目标出发分析可能性然后从起点开始一步步算到终点。第二步打家劫舍 —— 理解“状态定义”题目一排房子相邻不能同时偷求能偷到的最大金额。状态定义dp[i]表示偷到第i间房子时的最大金额。注意不一定非要偷第i间。递推公式的推导对于第i间房子有两种选择不偷金额等于dp[i-1]偷金额等于dp[i-2] nums[i]因为相邻不能偷所以只能从i-2转移过来所以dp[i] max(dp[i-1], dp[i-2] nums[i])我踩的坑我第一次写的时候边界条件写成了if n 1: return 1 # ❌ 应该是 return nums[0]别笑我当时真的以为返回1就行了。后来才发现如果只有一个房子应该返回它的金额而不是固定值1。滚动变量的应用由于递推只依赖前两个状态同样可以用滚动变量def rob(nums): if not nums: return 0 if len(nums) 1: return nums[0] prev2, prev1 nums[0], max(nums[0], nums[1]) for i in range(2, len(nums)): curr max(prev1, prev2 nums[i]) prev2, prev1 prev1, curr return prev1关键领悟状态定义决定了递推公式的写法。定义清楚了公式自然就出来了。第三步最大子数组和 —— 最折磨人的一道题目给定整数数组找出和最大的连续子数组返回其和。这道题为什么难前两道题的递推公式都比较直观但这道题的递推思路不太一样。它不是简单的“选或不选”而是要决定是否延续前面的子数组。状态定义dp[i]表示以nums[i]结尾的最大子数组和。注意子数组必须包含nums[i]。递推公式dp[i] max(nums[i], dp[i-1] nums[i])翻译成人话就是对于当前元素要么重新开始只取当前元素要么延续前面的子数组带上前面一起。我反复踩的坑这道题我折腾了很久核心问题就是在两个候选值里我总是下意识选小的那个。比如数组2 -1 4 -6 3第1步cur -1两个选项延续2 (-1) 1重新开始-1我选了-1。但明明1更大啊后来老师给了我一句口诀前面是负不如单干前面是正带上更猛。这句话的意思是如果上一步的dp[i-1]是负数那延续只会拖累当前元素不如重新开始如果是正数延续通常更有利。全负数的情况还有一个极端情况数组全是负数。比如-3 -1 -5 -2 -4。这时候每一步都应该选重新开始因为延续只会让负数变得更小。最终答案就是数组中最大的那个负数最接近0的那个。最终代码def maxSubArray(nums): prev nums[0] result nums[0] for num in nums[1:]: prev max(num, prev num) result max(result, prev) return result注意两点循环从第二个元素开始nums[1:]因为第一个元素已经在初始化时处理了result只记录历史最大值不是每一步都更新一个有用的比喻可以把这道题想象成做生意每天都有一个利润可能是正也可能是负你可以选择今天重新开张只算今天的利润也可以选择接着昨天的生意继续做加上今天的利润你的目标是找到某一段连续时间里的最大总利润如果昨天亏了今天重新开张更明智如果昨天赚了接着做更划算总结DP三步法经过这三道题的洗礼我总结出DP的通用步骤定义状态搞清楚dp[i]代表什么推导递推公式站在第i步思考可以从哪些状态转移过来确定初始条件和边界前几个状态怎么定特殊值怎么处理至于空间优化滚动变量那是锦上添花的事先把基本逻辑跑通再说。写在最后说实话最大子数组和这道题我差点放弃了。学了整整两天反复算错一度觉得自己不是学算法的料。但坚持下来之后发现所谓的“顿悟”其实就是把同一个道理想通了无数遍之后突然不再怀疑自己了。