从‘爬楼梯’到‘打家劫舍’一维DP的保姆级刷题路线图动态规划DP是算法学习中的一道分水岭也是许多开发者职业晋升路上的关键突破点。但面对LeetCode上琳琅满目的DP题目很多学习者常常陷入刷了就忘的困境。本文将构建一条循序渐进的一维DP学习路径通过题目之间的内在联系带你真正掌握DP的核心思想。1. 动态规划的本质认知动态规划不是某种具体的算法而是一种解决问题的思维方式。它的核心在于将复杂问题分解为相互关联的简单子问题并通过存储子问题的解来避免重复计算。理解这一点是打开DP大门的钥匙。在斐波那契数列问题中我们能看到DP最原始的模样def fib(n): if n 1: return n dp [0] * (n1) dp[1] 1 for i in range(2, n1): dp[i] dp[i-1] dp[i-2] return dp[n]这个简单的例子揭示了DP的五个核心要素状态定义dp[i]表示第i个斐波那契数转移方程dp[i] dp[i-1] dp[i-2]初始条件dp[0]0, dp[1]1计算顺序从i2开始顺序计算空间优化只需保存前两个状态提示理解DP的关键不在于记忆模板而在于培养将问题分解为子问题的思维方式。每次遇到新问题时先问自己这个问题的子问题是什么2. 基础篇线性DP三部曲2.1 LeetCode 70. 爬楼梯这是最经典的入门DP问题题目描述为每次可以爬1或2个台阶问爬到第n阶有多少种方法。状态转移方程与斐波那契数列惊人地相似dp[n] dp[n-1] dp[n-2]但它们的物理意义完全不同斐波那契数学定义爬楼梯实际问题的建模代码实现def climbStairs(n): if n 2: return n a, b 1, 2 for _ in range(3, n1): a, b b, ab return b2.2 爬楼梯变式三步问题当台阶选择扩展到1、2、3步时问题就变成了面试题08.01.三步问题dp[n] dp[n-1] dp[n-2] dp[n-3]这个变式帮助我们理解DP的可扩展性——当问题条件变化时只需调整转移方程。2.3 LeetCode 746. 使用最小花费爬楼梯这道题在基础爬楼梯上增加了成本维度状态定义需要包含最小花费def minCostClimbingStairs(cost): n len(cost) dp [0] * (n1) for i in range(2, n1): dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2]) return dp[n]这个进阶展示了DP问题的维度扩展能力我们需要在状态中增加新的考虑因素。3. 进阶篇状态定义的演化3.1 LeetCode 198. 打家劫舍这是线性DP的经典问题状态定义出现关键变化def rob(nums): n len(nums) if n 1: return nums[0] dp [0] * n dp[0], dp[1] nums[0], max(nums[0], nums[1]) for i in range(2, n): dp[i] max(dp[i-1], dp[i-2]nums[i]) return dp[-1]与爬楼梯系列相比打家劫舍的状态转移引入了选择与取舍的概念这是DP问题复杂度提升的重要标志。3.2 打家劫舍变式环形房屋LeetCode 213题将问题扩展为环形排列这需要我们对初始问题进行分类讨论不偷第一间房屋不偷最后一间房屋 然后取两种情况的最大值。3.3 LeetCode 740. 删除并获得点数这道题将打家劫舍的思想应用到更抽象的数值处理上展示了DP模型的抽象应用能力def deleteAndEarn(nums): max_num max(nums) points [0] * (max_num 1) for num in nums: points[num] num # 现在问题转化为打家劫舍 prev, curr 0, 0 for i in range(len(points)): prev, curr curr, max(curr, prev points[i]) return curr4. 高阶篇多维状态DP4.1 LeetCode 121. 买卖股票的最佳时机虽然这是一道简单题但它引入了状态机的思想def maxProfit(prices): min_price float(inf) max_profit 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit4.2 LeetCode 122. 买卖股票的最佳时机II允许多次交易后状态定义需要区分持有和未持有股票两种状态def maxProfit(prices): n len(prices) dp [[0]*2 for _ in range(n)] dp[0][1] -prices[0] for i in range(1, n): dp[i][0] max(dp[i-1][0], dp[i-1][1]prices[i]) dp[i][1] max(dp[i-1][1], dp[i-1][0]-prices[i]) return dp[-1][0]4.3 LeetCode 309. 最佳买卖股票时机含冷冻期增加了冷冻期后状态机变得更加复杂def maxProfit(prices): n len(prices) if n 2: return 0 dp [[0]*3 for _ in range(n)] dp[0][1] -prices[0] for i in range(1, n): dp[i][0] max(dp[i-1][0], dp[i-1][2]) # 不持有非冷冻 dp[i][1] max(dp[i-1][1], dp[i-1][0]-prices[i]) # 持有 dp[i][2] dp[i-1][1] prices[i] # 冷冻期 return max(dp[-1][0], dp[-1][2])5. 实战训练路线图为了系统掌握一维DP建议按照以下顺序刷题阶段题目核心训练点难度基础70.爬楼梯基本状态转移简单基础746.最小花费爬楼梯带权状态转移简单进阶198.打家劫舍选择型状态转移中等进阶213.打家劫舍II环形问题处理中等进阶740.删除并获得点数抽象建模能力中等高阶121.买卖股票单状态转移简单高阶122.买卖股票II双状态转移中等高阶309.买卖股票含冷冻期多状态转移中等在刷题过程中建议重点关注状态定义的合理性边界条件的处理空间优化的可能性问题变式之间的关联性动态规划的学习曲线虽然陡峭但通过这种系统化的专题突破方式配合对题目演变规律的深入理解相信每位开发者都能攻克这个算法难关。记住DP能力的提升不在于刷题数量而在于对每种变式背后统一模式的把握。