【算法学习专栏】动态规划基础·简单三题精讲（70.爬楼梯、118.杨辉三角、121.买卖股票的最佳时机）

引言动态规划Dynamic Programming简称DP是算法设计中的核心思想之一也是面试与竞赛中的高频考点。它通过将复杂问题分解为相互重叠的子问题并利用子问题的解构建原问题的解从而避免重复计算显著提升效率。对于初学者而言掌握动态规划的精髓往往从简单的经典题目开始通过理解状态定义、转移方程和边界条件这三大要素逐步建立解题直觉。本文精选力扣LeetCodehot100中三道简单难度的动态规划入门题目涵盖不同的应用场景70.爬楼梯一维线性递推斐波那契数列的典型变体118.杨辉三角二维矩阵递推组合数学的直观体现121.买卖股票的最佳时机状态机DP单状态转移与极值维护每道题目我们将按照题目概述→核心思路→复杂度分析→代码实现→优化讨论→面试考点的逻辑展开并在关键知识点处添加“注”形式的补充说明。文章最后给出动态规划在简单题目中的共性总结与学习建议。70.爬楼梯题目概述与链接题目链接70. Climbing Stairs问题描述假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。计算有多少种不同的方法可以爬到楼顶。示例输入n 2 输出2 解释有两种方法可以爬到楼顶。 1. 1 阶 1 阶 2. 2 阶 输入n 3 输出3 解释有三种方法可以爬到楼顶。 1. 1 阶 1 阶 1 阶 2. 1 阶 2 阶 3. 2 阶 1 阶核心解题思路爬楼梯问题是动态规划最经典的入门例题其本质是斐波那契数列的变体。定义状态dp[i]为“到达第i阶楼梯的不同方法数”。由于每次只能爬1或2阶要到达第i阶只能从第i-1阶爬1阶上来或者从第i-2阶爬2阶上来。因此状态转移方程为d p [ i ] d p [ i − 1 ] d p [ i − 2 ] dp[i] dp[i-1] dp[i-2]dp[i]dp[i−1]dp[i−2]边界条件dp[0] 1到达第0阶地面只有一种方法不动dp[1] 1到达第1阶只能爬1阶注有些实现将dp[0]设为1是为了让递推式在i2时成立dp[2] dp[1] dp[0] 1 1 2这与实际意义相符到达第2阶有两种方法11 或 2。注这里dp[0] 1是一种数学上的便利定义使得递推式统一。在实际问题中也可以直接从dp[1]和dp[2]开始计算避免对dp[0]的讨论。时间复杂度与空间复杂度分析时间复杂度O ( n ) O(n)O(n)。需要计算从2到n的每个dp[i]每次计算为常数时间加法。空间复杂度若使用长度为n1的数组O ( n ) O(n)O(n)若使用滚动变量仅保存前两个状态O ( 1 ) O(1)O(1)Python代码实现defclimbStairs(n:int)-int: 70.爬楼梯动态规划解法 ifn2:returnn# 方法1使用数组保存所有状态易于理解# dp [0] * (n 1)# dp[0], dp[1] 1, 1# for i in range(2, n 1):# dp[i] dp[i - 1] dp[i - 2]# return dp[n]# 方法2滚动数组优化空间O(1)prev1,prev21,1# prev1表示dp[i-1]prev2表示dp[i-2]foriinrange(2,n1):currprev1prev2 prev2,prev1prev1,curr# 滚动更新returnprev1# 测试用例if__name____main__:print(climbStairs(2))# 2print(climbStairs(3))# 3print(climbStairs(5))# 8代码注释边界处理当n 2时直接返回n因为dp[1]1, dp[2]2滚动数组实现用prev1和prev2分别记录前两个状态每次迭代更新将空间复杂度优化到O ( 1 ) O(1)O(1)关键代码段控制在20行以内突出动态规划的核心逻辑优化讨论空间优化如上所述使用滚动变量可将空间复杂度从O ( n ) O(n)O(n)降至O ( 1 ) O(1)O(1)。这是斐波那契类问题的常见优化技巧。数学优化爬楼梯问题本质是求斐波那契数列第n项可利用矩阵快速幂将时间复杂度降至O ( log ⁡ n ) O(\log n)O(logn)。递推关系可表示为[ d p [ i ] d p [ i − 1 ] ] [ 1 1 1 0 ] [ d p [ i − 1 ] d p [ i − 2 ] ] \begin{bmatrix} dp[i] \\ dp[i-1] \end{bmatrix} \begin{bmatrix} 1 1 \\ 1 0 \end{bmatrix} \begin{bmatrix} dp[i-1] \\ dp[i-2] \end{bmatrix}[dp[i]dp[i−1]​][11​10​][dp[i−1]dp[i−2]​]通过计算转移矩阵的n次幂可在对数时间内得到结果。但这在简单题目中通常不要求。变体思考若每次可以爬1、2或3个台阶则转移方程变为dp[i] dp[i-1] dp[i-2] dp[i-3]。推广到任意步长集合steps则成为完全背包问题每个步长可使用无限次。注当台阶数n很大时如n 10 7 n 10^7n107滚动数组优化是必要的否则内存可能溢出。此外结果可能超过32位整数范围需使用大整数或取模处理如题目要求结果对10 9 7 10^971097取模。面试考点状态定义能否清晰定义dp[i]的含义转移方程能否推导出dp[i] dp[i-1] dp[i-2]并解释原因边界条件正确处理dp[0]和dp[1]避免数组越界空间优化能否给出滚动数组的实现变体问题若步长变化或加入约束如“不能连续爬2阶”如何调整状态定义常见错误忘记处理n0或n1的边界情况错误地将dp[0]设为0导致dp[2]计算错误使用递归不加记忆化导致指数级时间复杂度118.杨辉三角题目概述与链接题目链接118. Pascal’s Triangle问题描述给定一个非负整数numRows生成杨辉三角的前numRows行。示例输入numRows 5 输出 [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]杨辉三角性质第i行从0开始有i1个元素每行首尾元素为1对于第i行第j个元素0 j i有triangle[i][j] triangle[i-1][j-1] triangle[i-1][j]第i行第j个元素等于组合数C i j C_i^jCij​核心解题思路杨辉三角是二维动态规划的典型例题其递推关系直接给出了状态转移方程。定义二维数组triangle其中triangle[i][j]表示第i行第j列的元素。状态转移方程边界条件triangle[i][0] triangle[i][i] 1内部元素triangle[i][j] triangle[i-1][j-1] triangle[i-1][j]其中1 ≤ j ≤ i-1动态规划过程初始化空列表triangle逐行生成对于第i行创建长度为i1的列表row设置首尾为1根据上一行的值计算中间元素将当前行加入结果注杨辉三角的递推关系体现了组合数的递推公式C n k C n − 1 k − 1 C n − 1 k C_n^k C_{n-1}^{k-1} C_{n-1}^kCnk​Cn−1k−1​Cn−1k​这是组合数学中的基本恒等式。时间复杂度与空间复杂度分析时间复杂度O ( numRows 2 ) O(\text{numRows}^2)O(numRows2)。总元素个数约为numRows ( numRows 1 ) 2 \frac{\text{numRows}(\text{numRows}1)}{2}2numRows(numRows1)​每个元素计算一次。空间复杂度O ( numRows 2 ) O(\text{numRows}^2)O(numRows2)用于存储整个三角形。若只要求输出而不存储可降至O ( numRows ) O(\text{numRows})O(numRows)只保存上一行。Python代码实现defgenerate(numRows:int): 118.杨辉三角动态规划解法 ifnumRows0:return[]triangle[]foriinrange(numRows):# 创建当前行长度为 i1row[1]*(i1)# 计算中间元素当 i 2 时才有中间元素forjinrange(1,i):row[j]triangle[i-1][j-1]triangle[i-1][j]triangle.append(row)returntriangle# 测试用例if__name____main__:resultgenerate(5)forrowinresult:print(row)# 输出# [1]# [1, 1]# [1, 2, 1]# [1, 3, 3, 1]# [1, 4, 6, 4, 1]代码注释边界处理当numRows 0时返回空列表核心循环外层i控制行号内层j计算中间元素利用triangle[i-1]获取上一行数据实现递推代码简洁关键逻辑控制在20行以内优化讨论空间优化如果只需要生成杨辉三角的某一行如第k行可使用滚动数组思想只保存上一行数据将空间复杂度降至O ( k ) O(k)O(k)。进一步利用对称性C n k C n n − k C_n^k C_n^{n-k}Cnk​Cnn−k​可减少一半计算。组合数计算杨辉三角第i行第j列就是组合数C i j C_i^jCij​。可直接用组合数公式计算C n k n ! k ! ( n − k ) ! C_n^k \frac{n!}{k!(n-k)!}Cnk​k!(n−k)!n!​但阶乘计算可能溢出且时间复杂度较高。对于较大n通常使用递推关系更稳妥。变体问题杨辉三角II只返回第k行从0开始杨辉三角中的路径和从顶部到底部的最小/最大路径和类似三角形最小路径和问题注杨辉三角在算法题中常作为动态规划入门题但其数学内涵丰富二项式定理、组合恒等式等。面试中可能要求解释递推关系的数学背景。面试考点二维DP定义能否正确构建二维状态表递推关系理解能否解释triangle[i][j] triangle[i-1][j-1] triangle[i-1][j]的数学意义边界处理正确处理首尾元素为1空间优化若只需求某一行如何优化空间组合数知识了解杨辉三角与组合数的关系常见错误索引混乱误用i和j导致数组越界忘记首尾赋值为1对numRows0或1的特殊情况处理不当121.买卖股票的最佳时机题目概述与链接题目链接121. Best Time to Buy and Sell Stock问题描述给定一个数组prices其中prices[i]表示第i天的股票价格。你只能选择某一天买入这支股票并选择在未来的某一天卖出。设计算法计算你所能获取的最大利润。如果你不能获取任何利润返回0。示例输入prices [7,1,5,3,6,4] 输出5 解释在第 2 天价格1买入在第 5 天价格6卖出利润6-15。 输入prices [7,6,4,3,1] 输出0 解释价格持续下跌无法获利。关键约束只能进行一次交易一次买入一次卖出卖出必须在买入之后可以当天买入当天卖出利润为0核心解题思路这是经典的“状态机”动态规划问题也可用贪心思想解决。定义状态dp[i]为“在前i天中进行一次交易能获得的最大利润”。但更高效的做法是维护历史最低价格min_price并在遍历过程中计算当前价格与历史最低的差值作为潜在利润。状态定义动态规划视角dp[i][0]第i天结束时持有股票的最大利润dp[i][1]第i天结束时不持有股票的最大利润但本题限制只能交易一次且状态可简化。贪心/一次遍历解法初始化min_price float(inf),max_profit 0遍历每天价格price更新历史最低价min_price min(min_price, price)计算当前卖出利润profit price - min_price更新最大利润max_profit max(max_profit, profit)返回max_profit动态规划解法扩展性更强dp[i] max(dp[i-1], prices[i] - min_price)其中min_price min(min_price, prices[i])注虽然本题可用贪心思想解决但其本质仍是动态规划——状态为“当前最大利润”转移方程为dp[i] max(dp[i-1], prices[i] - min_price)。这种简化得益于问题约束单次交易。时间复杂度与空间复杂度分析时间复杂度O ( n ) O(n)O(n)。只需一次遍历。空间复杂度贪心解法O ( 1 ) O(1)O(1)只使用常数变量动态规划数组O ( n ) O(n)O(n)若保存每天的最大利润Python代码实现defmaxProfit(prices): 121.买卖股票的最佳时机一次遍历贪心/DP解法 ifnotpricesorlen(prices)2:return0# 方法1直观贪心解法min_pricefloat(inf)max_profit0forpriceinprices:min_pricemin(min_price,price)profitprice-min_price max_profitmax(max_profit,profit)returnmax_profit# 方法2动态规划数组便于理解状态转移# n len(prices)# dp [0] * n # dp[i]表示前i天的最大利润# min_price prices[0]## for i in range(1, n):# min_price min(min_price, prices[i])# dp[i] max(dp[i-1], prices[i] - min_price)## return dp[-1]# 测试用例if__name____main__:print(maxProfit([7,1,5,3,6,4]))# 5print(maxProfit([7,6,4,3,1]))# 0print(maxProfit([1,2,3,4,5]))# 4代码注释边界处理数组为空或长度小于2时直接返回0无法交易贪心解法维护min_price和max_profit遍历中更新动态规划版本用数组dp记录每天的最大利润便于追踪状态变化两种方法本质相同贪心解法是动态规划的空间优化版本优化讨论空间优化如上所述贪心解法已将空间复杂度优化至O ( 1 ) O(1)O(1)是最优解。状态机DP的通用性本题的完整状态机DP解法为dp[i][0] max(dp[i-1][0], -prices[i])# 持有股票dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i])# 不持有股票其中dp[i][0]表示第i天持有股票的最大利润要么之前持有要么今天买入dp[i][1]表示第i天不持有股票的最大利润要么之前已卖出要么今天卖出。初始化dp[0][0] -prices[0],dp[0][1] 0。最终答案为dp[n-1][1]。这种解法虽然稍复杂但易于扩展到“多次交易”、“含冷冻期”、“含手续费”等变体问题。变体问题买卖股票的最佳时机II不限交易次数买卖股票的最佳时机III最多两次交易买卖股票的最佳时机IV最多k次交易含冷冻期卖出后有一天冷冻期不能买入含手续费每次交易需支付固定手续费注股票问题系列是动态规划的经典应用掌握状态机模型是解决此类问题的关键。建议从本题出发逐步学习更复杂的变体。面试考点问题转化能力能否将利润计算转化为“找最大差值”问题一次遍历解法能否设计O ( n ) O(n)O(n)时间、O ( 1 ) O(1)O(1)空间的算法边界条件处理价格递减、空数组等情况状态机DP理解能否给出完整的状态定义和转移方程变体扩展了解股票问题系列的其他变体常见错误误用“最大价格减最小价格”忽略时间顺序卖出必须在买入后忘记处理利润为0的情况价格持续下跌在价格数组很小时未做边界判断动态规划在简单题目中的共性总结通过以上三道题目的分析我们可以总结出动态规划解决简单问题的共性模式1. 状态定义爬楼梯一维状态dp[i]表示到达第i阶的方法数杨辉三角二维状态triangle[i][j]表示第i行第j列的值买卖股票可简化为一维状态dp[i]前i天最大利润或状态机dp[i][0/1]关键状态应能完整描述问题的某个阶段且包含做出决策所需的信息。2. 转移方程线性递推dp[i] dp[i-1] dp[i-2]爬楼梯二维递推triangle[i][j] triangle[i-1][j-1] triangle[i-1][j]杨辉三角极值维护dp[i] max(dp[i-1], prices[i] - min_price)买卖股票关键找出当前状态与之前状态的关系用数学公式表达。3. 边界条件爬楼梯dp[0] 1,dp[1] 1杨辉三角每行首尾为1买卖股票第一天利润为0历史最低价为第一天价格关键正确初始化初始状态避免递推起点错误。4. 空间优化滚动数组仅保存必要的前几个状态爬楼梯压缩状态用变量替代数组买卖股票对称性利用减少计算量杨辉三角关键识别状态依赖关系消除不必要的存储。5. 思维进阶从简单题目出发可向以下方向扩展增加维度如股票问题增加交易次数维度增加约束如爬楼梯增加“不能连续爬2阶”约束改变目标如杨辉三角求路径和而非生成整个三角学习建议从简单题目入手掌握状态定义、转移方程、边界条件这三要素理解优化本质空间优化不是炫技而是对状态依赖关系的深刻理解建立解题模板对常见DP类型线性、二维、状态机等形成思维框架多做变体练习同一核心思想在不同约束下的表现锻炼思维灵活性重视数学基础递推关系往往有深刻的数学背景如组合数、斐波那契