1. 动态规划入门：从爬楼梯问题开始

动态规划（Dynamic Programming）是算法面试中最常考察的解题方法之一，也是LeetCode Hot100中的高频题型。我第一次接触动态规划时，就是从经典的爬楼梯问题（T70）开始的。这个问题看似简单，却完美展现了动态规划的核心思想。

假设你正在爬楼梯，需要n阶才能到达楼顶。每次你可以爬1或2个台阶。有多少种不同的方法可以爬到楼顶？当我第一次看到这个问题时，直觉告诉我可以用递归解决：

def climbStairs(n): if n == 1: return 1 if n == 2: return 2 return climbStairs(n-1) + climbStairs(n-2)

但实际测试发现，当n=40时，这个解法需要近10秒才能得出结果。为什么？因为递归存在大量重复计算。比如计算climbStairs(5)需要计算climbStairs(4)和climbStairs(3)，而climbStairs(4)又要计算climbStairs(3)和climbStairs(2)，这里climbStairs(3)就被重复计算了。

提示：递归解法的时间复杂度是O(2^n)，呈指数级增长，这在算法中是完全不可接受的。

动态规划的精妙之处就在于它通过"记忆化"避免了重复计算。我们可以用一个数组dp来存储中间结果：

def climbStairs(n): if n == 1: return 1 dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2 for i in range(3, n + 1): 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, n + 1): first, second = second, first + second return second

这样空间复杂度就降到了O(1)。从这个问题中，我总结出动态规划解题的三个关键步骤：

1. 定义状态：dp[i]表示爬到第i阶的方法数
2. 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
3. 初始条件：dp[1] = 1, dp[2] = 2

2. 杨辉三角形：理解二维动态规划

杨辉三角形（T118）是另一个经典的动态规划问题，它帮助我们理解二维状态的定义。给定一个非负整数numRows，生成杨辉三角形的前numRows行。

我第一次尝试时，直接按照数学定义来写代码：

def generate(numRows): triangle = [] for row_num in range(numRows): row = [None for _ in range(row_num + 1)] row[0], row[-1] = 1, 1 for j in range(1, len(row) - 1): row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j] triangle.append(row) return triangle

这个解法虽然正确，但代码看起来有些复杂。后来我发现可以用动态规划的思路重构：

1. 状态定义：dp[i][j]表示第i行第j列的值
2. 状态转移方程：
   • dp[i][0] = dp[i][i] = 1
   • dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (0 < j < i)
3. 初始条件：dp[0][0] = 1

优化后的代码：

def generate(numRows): dp = [[1] * (i + 1) for i in range(numRows)] for i in range(2, numRows): for j in range(1, i): dp[i][j] = dp[i-1][j-1] + dp[i-1][j] return dp

在实际面试中，面试官可能会问："能否优化空间复杂度？"虽然这个问题返回的是整个三角形，理论上需要O(n^2)空间，但我们可以讨论只计算某一行的情况：

def getRow(rowIndex): row = [1] * (rowIndex + 1) for i in range(1, rowIndex): for j in range(i, 0, -1): row[j] += row[j - 1] return row

这个解法通过反向遍历避免了覆盖问题，空间复杂度降到了O(n)。

3. 打家劫舍：决策型动态规划

打家劫舍问题（T198）引入了决策的概念，难度上了一个台阶。题目描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，唯一制约因素是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

我第一次看到这个问题时，有点无从下手。后来通过分解子问题才找到思路：

1. 状态定义：dp[i]表示偷窃到第i个房屋时的最大金额
2. 状态转移方程：
   • 如果偷第i个房屋：dp[i] = dp[i-2] + nums[i]
   • 如果不偷第i个房屋：dp[i] = dp[i-1]
   • 取两者最大值：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
3. 初始条件：
   • dp[0] = nums[0]
   • dp[1] = max(nums[0], nums[1])

实现代码：

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, curr = 0, 0 for num in nums: prev, curr = curr, max(curr, prev + num) return curr

这个问题的变种很多，比如房屋排成环形（T213），或者房屋是二叉树结构（T337）。解决这些问题的关键在于理解状态转移方程的变化。

4. 动态规划的解题框架与常见误区

通过这三个经典问题，我总结出了一套动态规划的解题框架：

1. 确定dp数组及其下标的含义
2. 确定递推公式（状态转移方程）
3. 初始化dp数组
4. 确定遍历顺序
5. 举例推导dp数组

在实际解题中，我踩过不少坑，这里分享几个常见误区：

误区一：不定义清楚dp数组的含义刚开始时，我常常急于写代码而忽略明确定义dp[i]的含义。比如在打家劫舍问题中，必须明确dp[i]是考虑前i个房屋时的最大金额，而不是必须偷第i个房屋的金额。

误区二：初始化不完整在爬楼梯问题中，如果只初始化dp[1]=1而忘记dp[2]=2，当n=2时就会出错。我现在的习惯是先用小例子手动计算dp数组的前几项。

误区三：遍历顺序错误在二维dp问题中，有时需要先遍历行再遍历列，有时则相反。比如在背包问题中，如果使用一维dp数组，必须倒序遍历容量以避免重复计算。

误区四：空间优化过早虽然空间优化很重要，但在面试中，我建议先写出标准的dp解法，确保正确后再讨论优化。过早优化可能导致逻辑混乱。

为了巩固这些概念，我推荐按照以下顺序练习动态规划题目：

1. 基础问题：T70爬楼梯、T118杨辉三角形、T509斐波那契数
2. 路径问题：T62不同路径、T63不同路径II、T64最小路径和
3. 子序列问题：T300最长递增子序列、T1143最长公共子序列
4. 背包问题：T416分割等和子集、T494目标和
5. 高级问题：T72编辑距离、T121买卖股票的最佳时机系列

动态规划的学习曲线比较陡峭，但一旦掌握了核心思想，很多难题都会迎刃而解。我的经验是：从简单问题入手，手动推导dp数组的变化，理解每个状态转移方程背后的逻辑，逐步建立解题直觉。