1. 项目缘起一个看似简单的游戏为何值得深挖最近在整理一些经典的动态规划入门案例发现“小怪兽吃糖果”这个题目在各大算法社区和面试题库里出现的频率相当高。乍一看这不过是一个关于路径选择、累加求和的简单问题很多初学者甚至会觉得它有些“幼稚”。但当我真正带着学生和团队新人去拆解、实现并优化它时才发现这个“小怪兽”肚子里藏着不少东西。它绝不仅仅是一个求最大糖果数的练习。从最基础的暴力递归到引入记忆化的递归也就是常说的“自顶向下”动态规划再到最终优雅的“自底向上”递推这个题目完整地呈现了动态规划思想演进的经典路径。更重要的是在解决它的过程中我们会被迫思考几个关键问题状态如何定义状态之间如何转移边界条件怎么处理空间能不能优化这些问题是解决所有中等难度以上动态规划问题的通用钥匙。所以我决定把这次带人刷题的过程整理成文。我们不只追求一个能跑通的代码而是要像解一道数学证明题一样把“为什么这么做”的逻辑链条彻底理清。无论你是正在备战面试的求职者还是希望巩固算法基础的开发者相信通过这个具体的、有画面的案例你能对动态规划有一个更扎实、更直观的理解。2. 问题定义与场景还原小怪兽的糖果迷宫我们先抛开抽象的“动态规划”术语把问题还原成一个具体的、有画面感的场景。这样理解起来会容易得多。想象有一个m行n列的网格迷宫每一个格子里都放着数量不等的糖果。我们的主角——一只可爱的小怪兽——从迷宫的左上角也就是grid[0][0]出发它每次只能向右或者向下移动一格最终要到达迷宫的右下角grid[m-1][n-1]。小怪兽很贪吃它的目标是在从起点到终点的所有可能路径中找到一条能吃到最多糖果的路径并告诉我们这条路径上糖果的总数是多少。输入就是一个二维数组gridgrid[i][j]代表第i行、第j列格子里的糖果数量。假设所有糖果数量都是非负整数。输出就是一个整数即从左上角到右下角所能收集到的最大糖果总和。举个例子 假设迷宫grid如下[1, 3, 1] [1, 5, 1] [4, 2, 1]小怪兽从左上角1出发如果走路径 右 - 右 - 下 - 下 - 右即1 - 3 - 1 - 1 - 1总和是7。但显然这不是最优的。最优路径是 下 - 右 - 右 - 下 - 右即1 - 1 - 5 - 2 - 1总和是10。我们的算法就是要算出这个10。注意这里“只能向右或向下”的设定非常关键。它保证了路径不会走回头路也不会绕圈这使得问题具备了“无后效性”——未来下一步的决策只依赖于当前状态而不依赖于过去是如何到达这个状态的。这是能使用动态规划的一个核心前提。3. 暴力搜索最直观的笨办法及其致命缺陷拿到问题我们最本能的思路就是模拟小怪兽的所有走法然后比较哪条路糖果最多。这就是“暴力搜索”或者“深度优先搜索DFS”。我们可以定义一个递归函数dfs(i, j)它的含义是计算从位置(i, j)出发走到右下角终点(m-1, n-1)所能获得的最大糖果数。那么对于当前位置(i, j)小怪兽有两个选择向右走到达(i, j1)那么后续能获得的最大糖果数就是dfs(i, j1)。向下走到达(i1, j)那么后续能获得的最大糖果数就是dfs(i1, j)。小怪兽当然会选择未来收益更大的方向。所以从(i, j)出发能获得的最大总糖果数应该是当前格子的糖果grid[i][j]加上两个未来方向中更大的那个收益。于是我们有了递归关系dfs(i, j) grid[i][j] max(dfs(i, j1), dfs(i1, j))递归的终止条件边界是什么当小怪兽已经站在终点时它无路可走能获得的糖果就是终点格子的糖果本身dfs(m-1, n-1) grid[m-1][n-1]。另外当i或j超出网格边界时这是一个无效路径我们可以返回一个非常小的值比如-inf或者在实际代码中通过条件判断来避免进入无效位置。基于这个思路我们可以写出第一版代码以Python为例def max_candy_bruteforce(grid): m, n len(grid), len(grid[0]) def dfs(i, j): # 如果到达终点 if i m - 1 and j n - 1: return grid[i][j] # 如果超出边界返回负无穷大表示此路不通 if i m or j n: return float(-inf) # 计算向右和向下的最大收益 go_right dfs(i, j 1) go_down dfs(i 1, j) # 当前格子糖果 后续最大收益 return grid[i][j] max(go_right, go_down) return dfs(0, 0)这个方法的致命缺陷是什么——重复计算。让我们画一个很小的2x2网格来分析A B C D计算dfs(A)需要先计算dfs(B)和dfs(C)。 计算dfs(B)需要计算dfs(D)。 计算dfs(C)也需要计算dfs(D)。 你看dfs(D)被计算了两次在更大的网格中这种重复计算会呈指数级增长。对于一个m x n的网格粗略的时间复杂度是O(2^(mn))这是完全不可接受的。例如一个20x20的网格计算量已经是个天文数字。这就引出了动态规划的核心优化思想记忆化Memoization。既然dfs(D)的结果是确定的只取决于D本身以及它到终点的路径而这些是固定的那我们为什么不在第一次计算出dfs(D)时把它存起来下次需要时直接查表呢4. 记忆化搜索给递归装上“缓存”实现质的飞跃记忆化搜索常被称为“自顶向下”的动态规划。它保留了递归的直观逻辑但通过一个额外的存储结构通常是一个相同尺寸的二维数组我们叫它memo或dp来避免重复计算。我们定义memo[i][j]存储从位置(i, j)走到终点所能获得的最大糖果数。初始时我们把memo全部填充为一个特殊值比如-1表示该位置的结果还未被计算过。递归函数dfs(i, j)的逻辑几乎不变但在开始计算前先检查memo[i][j]如果memo[i][j] ! -1说明这个子问题之前已经算过了直接返回存储的结果。如果等于-1说明需要计算。计算完成后将结果存入memo[i][j]再返回。这样每个子问题每个格子都只会被计算一次。代码如下def max_candy_memoization(grid): m, n len(grid), len(grid[0]) # 初始化记忆化数组用 -1 表示未计算 memo [[-1] * n for _ in range(m)] def dfs(i, j): # 先查缓存 if memo[i][j] ! -1: return memo[i][j] # 边界/终点处理 if i m - 1 and j n - 1: memo[i][j] grid[i][j] elif i m or j n: memo[i][j] float(-inf) else: # 核心递推逻辑 go_right dfs(i, j 1) if j 1 n else float(-inf) go_down dfs(i 1, j) if i 1 m else float(-inf) memo[i][j] grid[i][j] max(go_right, go_down) return memo[i][j] return dfs(0, 0)为什么说这是一个巨大的飞跃时间复杂度从指数级O(2^(mn))降到了多项式级O(m * n)因为每个格子最多被计算一次。空间复杂度也是O(m * n)用于存储memo数组。对于绝大多数实际输入比如1000x1000的网格这已经是可解的了。实操心得一记忆化搜索是理解动态规划的“桥梁”。它让你在思考时依然沿着“我该如何解决这个大问题哦先解决它的小子问题”的自然递归思路同时通过缓存避免了性能灾难。在面试或实际解题中如果你一时想不出标准的递推公式先写出记忆化搜索的解法通常也能拿到大部分分数并且更容易向面试官解释你的思路。5. 标准动态规划自底向上构建递推的“金字塔”记忆化搜索很好但它本质上还是递归存在函数调用的开销并且对于某些极端深的递归虽然本题不会可能有栈溢出的风险。更经典、更标准的动态规划写法是“自底向上”的递推。“自底向上”是什么意思我们不再从起点开始问“从这出发能获得多少糖果”而是从终点开始反向思考或者更准确地说从最小的、已知的子问题开始逐步推导出更大的子问题的解。我们重新定义dp[i][j]数组但这次它的含义稍有不同通常定义为从起点(0, 0)走到位置(i, j)所能获得的最大糖果数。这个定义在“自底向上”递推中更常用也更直观。那么如何求dp[i][j]呢小怪兽要走到(i, j)它上一步只可能来自两个地方正上方(i-1, j)或者正左方(i, j-1)。它当然会选择糖果更多的那条路走过来。所以递推公式就出来了dp[i][j] grid[i][j] max(dp[i-1][j], dp[i][j-1])接下来是动态规划最关键的一步确定初始状态Base Case。起点dp[0][0]就是从起点到起点那糖果数就是grid[0][0]本身。第一行对于第一行(i0, j0)的格子小怪兽只能从左边来因为没有上一行所以dp[0][j] grid[0][j] dp[0][j-1]。第一列同理对于第一列(i0, j0)的格子小怪兽只能从上方来所以dp[i][0] grid[i][0] dp[i-1][0]。有了初始状态和递推公式我们就可以像搭积木一样从左到右、从上到下地遍历整个网格逐步填充dp数组。最终dp[m-1][n-1]就是我们想要的答案。def max_candy_dp(grid): if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) # 创建dp数组 dp [[0] * n for _ in range(m)] # 初始化起点 dp[0][0] grid[0][0] # 初始化第一行 for j in range(1, n): dp[0][j] dp[0][j-1] grid[0][j] # 初始化第一列 for i in range(1, m): dp[i][0] dp[i-1][0] grid[i][0] # 递推填充其余部分 for i in range(1, m): for j in range(1, n): dp[i][j] grid[i][j] max(dp[i-1][j], dp[i][j-1]) return dp[m-1][n-1]为什么“自底向上”更受青睐迭代代替递归完全避免了递归调用栈的开销和深度限制。清晰的流程代码结构非常规整就是两层循环逻辑一目了然。易于优化正如我们接下来要做的这种顺序遍历的递推很容易进行空间优化。实操心得二定义dp数组的含义是动态规划最核心的一步。dp[i][j]是表示“从起点到 (i,j) 的最大值”还是“从 (i,j) 到终点的最大值”这两种定义都可以但对应的递推公式和初始条件会完全不同。选择哪一个通常选择那个更容易写出递推公式、更容易初始化边界条件的定义。对于本题“从起点到 (i,j)”的定义使得递推从哪来非常自然。6. 空间优化将二维DP表压缩成一维数组观察上面的标准DP代码当我们计算dp[i][j]时只用到了它正上方dp[i-1][j]和正左方dp[i][j-1]的值。而dp[i][j-1]是我们在本行刚刚计算出来的新值。这意味着我们并不需要保存整个m x n的二维数组。在计算第i行时我们只需要一个一维数组dp_row用来保存上一行i-1行所有列的计算结果。在计算当前行时我们从左到右遍历dp_row[j]在更新前代表的是dp[i-1][j]上方的值而dp_row[j-1]在更新后代表的是dp[i][j-1]左方的值。我们可以就地更新dp_row数组。具体过程如下初始化dp_row为第一行的累加和因为第一行只能从左来。从第二行开始遍历。对于每一行的第一列j0它只能从上方来所以dp_row[0] grid[i][0]。对于每一行的其他列j0dp_row[j] grid[i][j] max(dp_row[j], dp_row[j-1])。这里的max(dp_row[j], dp_row[j-1])中dp_row[j]在未被当前行覆盖时存储的是上一行同列的值即“上方”的值。dp_row[j-1]在当前行计算中已经被更新存储的是本行前一列的值即“左方”的值。处理完所有行后dp_row的最后一个元素就是答案。def max_candy_dp_optimized(grid): if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) # 初始化dp_row为第一行的路径和 dp_row [0] * n dp_row[0] grid[0][0] for j in range(1, n): dp_row[j] dp_row[j-1] grid[0][j] # 从第二行开始递推 for i in range(1, m): # 更新当前行第一列的值只能从上方来 dp_row[0] dp_row[0] grid[i][0] for j in range(1, n): # dp_row[j] 是上一行同列的值上方dp_row[j-1]是本行前一列的值左方 dp_row[j] grid[i][j] max(dp_row[j], dp_row[j-1]) return dp_row[-1]空间复杂度从O(m*n)降到了O(n)这在处理大规模数据时优势明显。这是一个非常经典且实用的优化技巧。实操心得三空间优化不是炫技而是有实际意义的。当网格非常大时例如上百万个单元格O(m*n)的二维数组可能占用几百MB甚至上GB的内存而O(n)的数组可能只占几MB。在进行优化时一定要画图理解数据依赖关系。在本例中画出一个3x3的网格手动模拟一下一维数组dp_row在每一行计算时的变化你会对这个优化技巧的理解深刻十倍。7. 路径回溯如何记录小怪兽的最优行走路线前面的算法只告诉我们最大糖果数是多少但小怪兽具体是怎么走的在实际应用中我们往往不仅需要知道最优值还需要知道达成这个最优值的具体方案即路径。这就需要我们在动态规划的过程中额外记录“选择”。我们引入一个同样大小的二维数组path或choice。choice[i][j]可以记录走到(i, j)时是从哪个方向来的‘U’代表来自上方Up’L‘代表来自左方Left。修改标准DP代码在更新dp[i][j]时同时记录选择def max_candy_with_path(grid): if not grid or not grid[0]: return 0, [] m, n len(grid), len(grid[0]) dp [[0] * n for _ in range(m)] # 用于记录路径来源U来自上方L来自左方S起点 choice [[] * n for _ in range(m)] # 初始化起点 dp[0][0] grid[0][0] choice[0][0] S # 初始化第一行只能从左来 for j in range(1, n): dp[0][j] dp[0][j-1] grid[0][j] choice[0][j] L # 初始化第一列只能从上来 for i in range(1, m): dp[i][0] dp[i-1][0] grid[i][0] choice[i][0] U # 递推 for i in range(1, m): for j in range(1, n): from_up dp[i-1][j] from_left dp[i][j-1] if from_up from_left: dp[i][j] grid[i][j] from_up choice[i][j] U else: dp[i][j] grid[i][j] from_left choice[i][j] L # 回溯路径 path [] i, j m - 1, n - 1 while choice[i][j] ! S: # 回溯到起点为止 path.append((i, j)) if choice[i][j] U: i - 1 else: # L j - 1 path.append((0, 0)) # 加入起点 path.reverse() # 反转让路径从起点到终点 return dp[m-1][n-1], path调用这个函数除了得到最大糖果数还能得到一个坐标列表如[(0,0), (1,0), (1,1), (2,1), (2,2)]这就是小怪兽的最优行走路线。注意当来自上方和左方的糖果数相同时from_up from_left可能存在多条最优路径。上面的代码默认选择了来自上方的路径的判断你可以根据需求调整比如随机选择或者记录所有可能路径这需要更复杂的数据结构如列表来存储多个来源。8. 变种与扩展当问题条件发生变化时“小怪兽吃糖果”是一个模型很多实际问题都可以抽象成它。理解基础模型后面对变种就能从容应对。这里列举几个常见的变种及思路变种一最小初始糖果数LeetCode 174. Dungeon Game问题不再是求最大收益而是求从起点到终点保证生命值始终为正所需的最小初始生命值。此时dp[i][j]的定义需要变为从(i, j)走到终点所需的最小初始生命值。递推方向从终点反向推到起点递推公式变为dp[i][j] max(1, min(dp[i1][j], dp[i][j1]) - dungeon[i][j])。这彻底颠覆了“从哪来”的思路变成了“到哪去”并且要保证过程中的最小值约束。变种二带有障碍物的网格LeetCode 63. Unique Paths II网格中某些格子有障碍物糖果数为负无穷或标记为不可达小怪兽不能进入。处理方式很简单在初始化dp数组和递推时如果grid[i][j]是障碍物则直接将dp[i][j]设为0表示没有路径能到达这里或者对于求路径数的问题到达此点的路径数为0。在递推公式中来自障碍物格子的值不应被考虑。变种三方向扩展可以向右、向下、向右下如果小怪兽可以向右、向下、向右下移动那么递推公式就变为dp[i][j] grid[i][j] max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])只需要在计算时多考虑一个来源左上方即可。边界条件需要额外小心处理i-1和j-1同时有效的区域。变种四求路径数量LeetCode 62. Unique Paths如果不关心糖果数只关心有多少条不同的路径能从左上角走到右下角。那么dp[i][j]就定义为到达(i, j)的路径数。递推公式变为dp[i][j] dp[i-1][j] dp[i][j-1]因为到达(i, j)的路径必然是从上面或左边过来的所以路径数是两者之和。初始化时第一行和第一列的所有格子路径数都是1因为只有一条直线路径。面对变种核心是重新审视并准确定义dp数组的含义然后根据新的规则移动方式、目标函数是最大/最小/计数、有无约束条件来推导新的状态转移方程和边界条件。