1. 动态规划入门三部曲从斐波那契到爬楼梯问题作为一名经历过多次算法面试洗礼的老程序员我始终认为动态规划DP是区分普通开发者和算法高手的分水岭。今天要讨论的这三个题目——斐波那契数、爬楼梯和最小花费爬楼梯正是动态规划领域最经典的入门三部曲。它们看似简单却蕴含着DP最核心的思想精髓。记得我最初接触DP时曾被各种状态转移方程搞得晕头转向。直到某天深夜当我反复推导这三个基础问题后突然有种豁然开朗的感觉。这三个题目就像俄罗斯套娃层层递进地揭示了DP的本质将复杂问题分解为重叠子问题通过记忆化存储避免重复计算。2. 509. 斐波那契数动态规划的Hello World2.1 问题定义与暴力递归解法斐波那契数列的定义简单明了F(0) 0F(1) 1F(n) F(n-1) F(n-2), n 2最直观的解法是递归def fib(n): if n 1: return n return fib(n-1) fib(n-2)但这种方法存在严重的效率问题。以计算fib(5)为例调用树如下fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1)可以看到fib(3)被计算了两次fib(2)被计算了三次。时间复杂度达到O(2^n)空间复杂度O(n)。2.2 记忆化搜索与动态规划优化这就是动态规划要解决的核心问题——重叠子问题。我们可以通过两种方式优化方法一记忆化递归自顶向下memo {0:0, 1:1} def fib(n): if n not in memo: memo[n] fib(n-1) fib(n-2) return memo[n]方法二迭代法自底向上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]两种方法都将时间复杂度降到了O(n)空间复杂度O(n)。但我们可以进一步优化空间def fib(n): if n 1: return n prev, curr 0, 1 for _ in range(2, n1): prev, curr curr, prev curr return curr这个版本空间复杂度仅为O(1)是面试中最受青睐的写法。关键理解动态规划的核心在于发现重叠子问题并避免重复计算。斐波那契数列是理解这一概念的完美起点。3. 70. 爬楼梯斐波那契的变种3.1 问题转化与状态定义爬楼梯问题描述每次可以爬1或2个台阶有多少种方法爬到第n阶仔细分析会发现这与斐波那契数列惊人地相似到达第n阶的方法数 到达第n-1阶的方法数最后一步爬1阶 到达第n-2阶的方法数最后一步爬2阶状态转移方程 dp[n] dp[n-1] dp[n-2]初始条件 dp[0] 1 (地面算作一种方法) dp[1] 13.2 实现与优化直接套用斐波那契的优化思路def climbStairs(n): if n 2: return n prev, curr 1, 2 for _ in range(3, n1): prev, curr curr, prev curr return curr3.3 扩展思考如果每次可以爬1、2或3阶呢此时状态转移方程变为 dp[n] dp[n-1] dp[n-2] dp[n-3]这种变种问题在面试中经常出现考察的是对DP思想的理解深度而非死记硬背。4. 746. 使用最小花费爬楼梯引入代价因素4.1 问题升级与状态重新定义现在的问题变为每级台阶都有一个cost[i]支付该费用后可以选择爬1或2阶。可以从0或1阶开始求达到顶部的最小花费。关键点在于到达i阶的最小花费 min(到达i-1阶的最小花费 cost[i-1], 到达i-2阶的最小花费 cost[i-2])最终目标是到达第n阶即cost数组长度1状态转移方程 dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2])初始条件 dp[0] 0 (可以从0阶开始初始无花费) dp[1] 0 (也可以从1阶开始)4.2 代码实现与空间优化基础DP解法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]空间优化版def minCostClimbingStairs(cost): prev, curr 0, 0 for i in range(2, len(cost)1): prev, curr curr, min(curr cost[i-1], prev cost[i-2]) return curr4.3 常见错误与边界情况错误地将dp[1]初始化为cost[0]忽略了可以从1阶直接开始的情况忘记最终目标是n阶而非n-1阶对于空数组或单元素数组的处理5. 动态规划解题的通用思维框架通过这三个经典问题我们可以总结出解决DP问题的通用步骤定义状态明确dp[i]表示什么斐波那契中的F(i)爬楼梯中的方法数最小花费中的累计成本确定转移方程如何用之前的状态推导当前状态设置初始条件dp[0]、dp[1]等的值考虑优化是否可以压缩空间复杂度处理边界n0,1等特殊情况在实际面试中我建议按照以下顺序思考先想暴力递归解法画出递归树发现重叠子问题改用记忆化搜索转化为迭代形式的DP最后考虑空间优化6. 从这三个问题到更复杂的DP问题掌握了这三个基础问题后可以尝试解决更复杂的DP问题背包问题01背包、完全背包最长公共子序列股票买卖问题打家劫舍问题这些问题的核心思想都是一致的——定义状态、找到状态转移关系、处理初始条件和边界情况。我在刷题过程中发现很多DP难题其实都是这几个基础问题的变种或组合。比如打家劫舍问题就融合了爬楼梯和最小花费的思想。7. 算法训练中的实战建议不要死记硬背理解状态转移的本质比记住代码更重要画图辅助对于新问题先画递归树或状态转移图循序渐进从一维DP开始逐步过渡到二维DP反复练习这三个基础问题建议手写实现5遍以上直到能闭眼写出最优解对比分析比较这三个问题的异同点理解DP的灵活性在代码随想录的训练营中我发现很多同学在DP问题上容易犯两个极端错误要么过度依赖记忆要么完全回避DP。实际上DP就像游泳需要在理解原理的基础上通过大量练习来培养直觉。