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)但实际测试发现当n40时这个解法需要近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)。从这个问题中我总结出动态规划解题的三个关键步骤定义状态dp[i]表示爬到第i阶的方法数状态转移方程dp[i] dp[i-1] dp[i-2]初始条件dp[1] 1, dp[2] 22. 杨辉三角形理解二维动态规划杨辉三角形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这个解法虽然正确但代码看起来有些复杂。后来我发现可以用动态规划的思路重构状态定义dp[i][j]表示第i行第j列的值状态转移方程dp[i][0] dp[i][i] 1dp[i][j] dp[i-1][j-1] dp[i-1][j] (0 j i)初始条件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引入了决策的概念难度上了一个台阶。题目描述你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金唯一制约因素是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你不触动警报装置的情况下一夜之内能够偷窃到的最高金额。我第一次看到这个问题时有点无从下手。后来通过分解子问题才找到思路状态定义dp[i]表示偷窃到第i个房屋时的最大金额状态转移方程如果偷第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])初始条件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. 动态规划的解题框架与常见误区通过这三个经典问题我总结出了一套动态规划的解题框架确定dp数组及其下标的含义确定递推公式状态转移方程初始化dp数组确定遍历顺序举例推导dp数组在实际解题中我踩过不少坑这里分享几个常见误区误区一不定义清楚dp数组的含义刚开始时我常常急于写代码而忽略明确定义dp[i]的含义。比如在打家劫舍问题中必须明确dp[i]是考虑前i个房屋时的最大金额而不是必须偷第i个房屋的金额。误区二初始化不完整在爬楼梯问题中如果只初始化dp[1]1而忘记dp[2]2当n2时就会出错。我现在的习惯是先用小例子手动计算dp数组的前几项。误区三遍历顺序错误在二维dp问题中有时需要先遍历行再遍历列有时则相反。比如在背包问题中如果使用一维dp数组必须倒序遍历容量以避免重复计算。误区四空间优化过早虽然空间优化很重要但在面试中我建议先写出标准的dp解法确保正确后再讨论优化。过早优化可能导致逻辑混乱。为了巩固这些概念我推荐按照以下顺序练习动态规划题目基础问题T70爬楼梯、T118杨辉三角形、T509斐波那契数路径问题T62不同路径、T63不同路径II、T64最小路径和子序列问题T300最长递增子序列、T1143最长公共子序列背包问题T416分割等和子集、T494目标和高级问题T72编辑距离、T121买卖股票的最佳时机系列动态规划的学习曲线比较陡峭但一旦掌握了核心思想很多难题都会迎刃而解。我的经验是从简单问题入手手动推导dp数组的变化理解每个状态转移方程背后的逻辑逐步建立解题直觉。 
长河君 · 2026/10/29 23:09:43 · 阅读 1.2k 动态规划入门：从爬楼梯到打家劫舍实战解析
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)但实际测试发现当n40时这个解法需要近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)。从这个问题中我总结出动态规划解题的三个关键步骤定义状态dp[i]表示爬到第i阶的方法数状态转移方程dp[i] dp[i-1] dp[i-2]初始条件dp[1] 1, dp[2] 22. 杨辉三角形理解二维动态规划杨辉三角形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这个解法虽然正确但代码看起来有些复杂。后来我发现可以用动态规划的思路重构状态定义dp[i][j]表示第i行第j列的值状态转移方程dp[i][0] dp[i][i] 1dp[i][j] dp[i-1][j-1] dp[i-1][j] (0 j i)初始条件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引入了决策的概念难度上了一个台阶。题目描述你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金唯一制约因素是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你不触动警报装置的情况下一夜之内能够偷窃到的最高金额。我第一次看到这个问题时有点无从下手。后来通过分解子问题才找到思路状态定义dp[i]表示偷窃到第i个房屋时的最大金额状态转移方程如果偷第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])初始条件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. 动态规划的解题框架与常见误区通过这三个经典问题我总结出了一套动态规划的解题框架确定dp数组及其下标的含义确定递推公式状态转移方程初始化dp数组确定遍历顺序举例推导dp数组在实际解题中我踩过不少坑这里分享几个常见误区误区一不定义清楚dp数组的含义刚开始时我常常急于写代码而忽略明确定义dp[i]的含义。比如在打家劫舍问题中必须明确dp[i]是考虑前i个房屋时的最大金额而不是必须偷第i个房屋的金额。误区二初始化不完整在爬楼梯问题中如果只初始化dp[1]1而忘记dp[2]2当n2时就会出错。我现在的习惯是先用小例子手动计算dp数组的前几项。误区三遍历顺序错误在二维dp问题中有时需要先遍历行再遍历列有时则相反。比如在背包问题中如果使用一维dp数组必须倒序遍历容量以避免重复计算。误区四空间优化过早虽然空间优化很重要但在面试中我建议先写出标准的dp解法确保正确后再讨论优化。过早优化可能导致逻辑混乱。为了巩固这些概念我推荐按照以下顺序练习动态规划题目基础问题T70爬楼梯、T118杨辉三角形、T509斐波那契数路径问题T62不同路径、T63不同路径II、T64最小路径和子序列问题T300最长递增子序列、T1143最长公共子序列背包问题T416分割等和子集、T494目标和高级问题T72编辑距离、T121买卖股票的最佳时机系列动态规划的学习曲线比较陡峭但一旦掌握了核心思想很多难题都会迎刃而解。我的经验是从简单问题入手手动推导dp数组的变化理解每个状态转移方程背后的逻辑逐步建立解题直觉。