1. 从一道经典DP题说起棋盘上的金币收集最近在整理蓝桥杯的历年真题翻到了ALGO-1006这道“拿金币”的题目。这题可以说是动态规划Dynamic Programming DP入门的一道“样板题”它把DP最核心的“状态定义”和“状态转移”思想放在了一个非常直观的棋盘模型里。很多朋友初学DP时总觉得概念抽象公式难记但如果你能亲手把这道题从暴力递归优化到记忆化搜索再到标准的二维DP递推最后可能还能压成一维数组整个思路打通了DP的门槛也就跨过去了一大半。这道题本身描述很简单在一个N x N的棋盘上每个格子放着若干金币你从左上角出发每次只能向右或向下走一步最终到达右下角。问你一路上能拿到的最大金币总数是多少今天我们就来彻底拆解这道题不止于AC更要弄懂每一个优化步骤背后的“为什么”。2. 问题本质与暴力搜索的困境首先我们得把问题模型抽象出来。给定一个N x N的二维数组grid其中grid[i][j]表示棋盘第 i 行、第 j 列格子里的金币数量这里我们约定行和列都从0开始计数。你从(0, 0)出发要到达(N-1, N-1)。每次移动你只能选择向右走(i, j1)或者向下走(i1, j)。你的目标是找到一条路径使得路径上经过的所有格子的金币总和最大。最直接的想法是什么回溯或者叫深度优先搜索DFS。我们模拟这个人从起点开始每一个位置都尝试向右走和向下走把所有可能的路径都走一遍然后比较哪条路径的金币总和最大。我们可以写一个递归函数dfs(i, j)它的含义是从位置(i, j)出发走到终点(N-1, N-1)所能获得的最大金币数注意这个定义很重要是后续所有优化的基础。那么对于当前位置(i, j)我首先拿到这里的金币grid[i][j]。接下来我有两种选择向右走那么后续能获得的最大金币就是dfs(i, j1)。向下走那么后续能获得的最大金币就是dfs(i1, j)。我当然要选收益更大的那条路。所以从(i, j)出发能获得的最大总金币数就是grid[i][j]加上dfs(i, j1)和dfs(i1, j)中的较大值。递归的终止条件就是当(i, j)已经到达终点时直接返回grid[N-1][N-1]。写成伪代码大概是这样def dfs(i, j): # 如果到达终点 if i N-1 and j N-1: return grid[i][j] # 如果走到棋盘外返回一个很小的值表示此路不通 if i N or j N: return -float(inf) # 拿到当前格子的金币 current_gold grid[i][j] # 计算向右和向下走的最大收益 go_right dfs(i, j1) go_down dfs(i1, j) # 选择收益更大的方向加上当前金币 return current_gold max(go_right, go_down)最终答案就是调用dfs(0, 0)。这个思路完全正确但为什么不行呢因为它的时间复杂度是指数级的。对于一个N x N的棋盘从左上角到右下角一共需要走(N-1) (N-1) 2N-2步其中必须向右走N-1步向下走N-1步。路径总数是一个组合数C(2N-2, N-1)。当 N10 时这个数大约是 48620当 N20 时就暴涨到约 3.5e10三百五十亿条路径。递归树会庞大到无法计算这就是所谓的“暴力搜索困境”。注意这里递归函数的定义dfs(i, j)是“从(i,j)到终点的最大收益”这是一种“自顶向下”的思考方式。后续我们将其转化为DP时会采用更容易理解的“自底向上”的递推但核心的状态定义是相通的。3. 重叠子问题与记忆化搜索给递归加上备忘录暴力搜索慢在哪里慢在大量的重复计算。我们仔细观察递归树。假设棋盘是 3x3计算dfs(0,0)需要计算dfs(0,1)和dfs(1,0)。而计算dfs(0,1)时又会去计算dfs(0,2)和dfs(1,1)。计算dfs(1,0)时也会去计算dfs(1,1)和dfs(2,0)。看到了吗dfs(1,1)被计算了两次在更大的棋盘中像dfs(1,1)这样的中间状态会被重复计算成千上万次。这就是动态规划问题第一个关键特征重叠子问题。既然子问题被重复计算那我们何不把第一次计算的结果存起来呢这就是记忆化搜索Memoization。我们引入一个和棋盘同样大小的二维数组memomemo[i][j]专门用来记录dfs(i, j)的计算结果。在递归函数开始时先检查memo[i][j]是否已经计算过例如初始化为一个特殊值如-1表示未计算如果计算过就直接返回存储的结果。如果没有计算过才执行递归计算并在返回前将结果存入memo[i][j]。记忆化搜索的伪代码改进如下def dfs(i, j): # 如果到达终点 if i N-1 and j N-1: return grid[i][j] # 如果走到棋盘外返回一个很小的值 if i N or j N: return -float(inf) # 检查备忘录 if memo[i][j] ! -1: return memo[i][j] # 计算 current_gold grid[i][j] go_right dfs(i, j1) go_down dfs(i1, j) # 将结果存入备忘录 memo[i][j] current_gold max(go_right, go_down) return memo[i][j]这个改进是革命性的。现在每个状态(i, j)最多只被计算一次。总共有N x N个状态每个状态的计算是常数时间两次递归调用和一次max比较。因此时间复杂度从指数级降到了O(N²)空间复杂度也是 O(N²)用于存储备忘录和递归调用栈。对于 N1000 的棋盘这个算法也可以在合理时间内完成。记忆化搜索是理解DP的绝佳桥梁。它本质上就是递归 缓存。它保留了递归“自顶向下”的天然思维模式从大问题分解到小问题同时通过备忘录避免了重复计算。很多复杂的DP问题直接想递推公式可能很困难但先用记忆化搜索的思路把状态定义和转移方程想清楚会容易得多。4. 标准的二维DP递推自底向上的表格填充记忆化搜索已经足够好了但它仍然依赖于递归存在函数调用的开销和栈深度的限制虽然对于此题栈深度最大为 2N通常不是问题。我们可以更进一步将其转化为更标准的、迭代式的动态规划也就是常说的“填表法”。记忆化搜索是“我需要dfs(i,j)那我就去算算完存起来”。而递推DP是“我知道所有子问题的答案我就能算出当前问题的答案”。我们需要找到一个正确的计算顺序。让我们重新定义状态dp[i][j]。为了和递推顺序更匹配我们这次将其定义为从起点(0, 0)走到位置(i, j)所能获得的最大金币数。注意这个定义和之前记忆化搜索的定义是反向的但它们是等价的只是思考方向不同。现在我们的目标是求出dp[N-1][N-1]。那么dp[i][j]怎么求呢要走到(i, j)上一步只能从左边(i, j-1)过来或者从上面(i-1, j)过来。因为规则只允许向右或向下走。所以走到(i, j)的最大金币数就等于从起点到上一步位置的最大金币数加上(i, j)本身的金币数并在两个来源中选大的那个。因此状态转移方程为dp[i][j] grid[i][j] max(dp[i-1][j], dp[i][j-1])现在我们需要一个计算顺序。观察方程要算dp[i][j]需要知道dp[i-1][j]上一行和dp[i][j-1]左边一列。这提示我们可以按行遍历从左到右计算。这样当计算到(i, j)时(i-1, j)和(i, j-1)肯定都已经计算出来了。还有边界情况需要处理第一行i0和第一列j0。对于第一行(0, j)它只能从左边(0, j-1)过来因为没有上一行。所以dp[0][j] grid[0][j] dp[0][j-1]。对于第一列(i, 0)它只能从上面(i-1, 0)过来因为没有左边一列。所以dp[i][0] grid[i][0] dp[i-1][0]。起点(0, 0)就是dp[0][0] grid[0][0]。我们可以初始化一个N x N的dp数组然后按上述规则填充# 初始化dp数组 dp [[0] * N for _ in range(N)] # 初始化起点 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, N): dp[i][0] dp[i-1][0] grid[i][0] # 递推填充其余部分 for i in range(1, N): for j in range(1, N): dp[i][j] grid[i][j] max(dp[i-1][j], dp[i][j-1]) # 答案 answer dp[N-1][N-1]这个算法的时间复杂度是 O(N²)需要遍历整个棋盘一次。空间复杂度也是 O(N²)用于存储dp表。这就是最经典的二维DP解法思路清晰代码规整是竞赛和面试中的标准写法。5. 空间优化滚动数组与一维DP二维DP已经很快了但我们还能在空间上做优化。观察状态转移方程dp[i][j] grid[i][j] max(dp[i-1][j], dp[i][j-1])。计算第i行的dp值时我们只用到了当前行已经计算过的左边元素dp[i][j-1]同一行。上一行同列的元素dp[i-1][j]。这意味着在计算过程中我们并不需要保存整个N x N的dp表。我们只需要保存“上一行”的dp值以及“当前行”已经计算出来的部分dp值。我们可以只用一个一维数组dp来解决问题。在这个优化中dp[j]在计算第i行时代表什么含义呢它需要同时扮演两个角色在max(dp[i-1][j], dp[i][j-1])中dp[i-1][j]是“旧的”dp[j]在计算第i行之前的值。dp[i][j-1]是“新的”dp[j-1]在同一行i中刚刚计算出来的左边那个值。所以当我们按行遍历从左到右计算时递推公式可以改写为新的dp[j] grid[i][j] max(旧的dp[j], 新的dp[j-1])这里的“旧的dp[j]”就是上一行第j列的结果“新的dp[j-1]”就是本行第j-1列刚刚更新完的结果。我们可以在原数组上直接更新。具体步骤如下初始化一个长度为N的一维数组dp。处理第一行dp[0] grid[0][0]然后for j in range(1, N): dp[j] dp[j-1] grid[0][j]。这和二维DP初始化第一行逻辑一样。从第二行开始遍历 (i from 1 to N-1)每一行的第一个元素j0只能从上方来所以先更新dp[0] dp[0] grid[i][0]。这里的dp[0]在更新前代表上一行第一列的值更新后代表本行第一列的值。然后从左到右j from 1 to N-1更新dp[j] grid[i][j] max(dp[j], dp[j-1])。注意等号右边的dp[j]是上一行的值dp[j-1]是本行已经更新过的左边邻居的值。# 初始化一维dp数组代表第一行的结果 dp [0] * N dp[0] grid[0][0] for j in range(1, N): dp[j] dp[j-1] grid[0][j] # 从第二行开始递推 for i in range(1, N): # 更新本行第一列 dp[0] dp[0] grid[i][0] # 更新本行后续列 for j in range(1, N): dp[j] grid[i][j] max(dp[j], # 上一行同列的值 dp[j-1]) # 本行左边的值 # 答案 answer dp[N-1]这个算法的时间复杂度依然是 O(N²)但空间复杂度从 O(N²) 优化到了 O(N)。这在N很大时能有效节省内存。这种技巧被称为“滚动数组”是DP空间优化的常见手段。实操心得一维DP的写法需要对状态的含义有更清晰的理解特别是dp[j]在更新前后代表的不同含义。在纸上画一个两行的例子手动模拟一下更新过程是理解这个技巧最快的方法。很多类似的网格路径DP问题比如最小路径和问题都可以用这个思路优化。6. 路径回溯如何记录最优路径上面的解法只告诉我们最大金币数是多少但有时候题目会要求输出这条最优路径本身。这就需要我们在动态规划的过程中额外记录“选择”信息。我们可以在进行状态转移时用一个同样大小的二维数组path来记录每一步的选择。path[i][j]可以存储一个值指示到达(i, j)的最优路径是从哪个方向来的。例如用‘L’表示从左方来(i, j-1)用‘U’表示从上方来(i-1, j)。对于起点(0,0)可以标记为‘S’。修改二维DP的代码dp [[0]*N for _ in range(N)] path [[None]*N for _ in range(N)] # 记录路径来源 dp[0][0] grid[0][0] path[0][0] S # Start # 初始化第一行只能从左来 for j in range(1, N): dp[0][j] dp[0][j-1] grid[0][j] path[0][j] L # 初始化第一列只能从上来 for i in range(1, N): dp[i][0] dp[i-1][0] grid[i][0] path[i][0] U # 递推 for i in range(1, N): 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 path[i][j] U else: dp[i][j] grid[i][j] from_left path[i][j] L # 回溯路径 i, j N-1, N-1 optimal_path [] while path[i][j] ! S: optimal_path.append((i, j)) if path[i][j] U: i - 1 else: # L j - 1 optimal_path.append((0, 0)) optimal_path.reverse() # 从起点到终点的顺序回溯时我们从终点(N-1, N-1)开始根据path数组记录的来源方向不断向前一个格子回溯直到起点。最后将路径反转就得到了从起点到终点的顺序。注意事项当from_up from_left时说明两条路径收益相同此时选择任意一条都可以。在记录路径时需要约定一个优先规则比如优先‘U’以保证输出确定性的路径。另外如果使用一维DP进行空间优化想要回溯完整路径会非常困难因为历史选择信息被覆盖了。所以当需要输出路径时通常保留二维DP表是更简单直接的选择。7. 举一反三变种问题与思维扩展“拿金币”的模型非常基础但掌握了它可以解决一大类问题。这里列举几个常见的变种帮助你深化理解变种1最小路径和如果把“金币数”换成“路径代价”求从左上角到右下角的“最小路径和”解法完全一样只需把状态转移方程中的max改为min即可。dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])。变种2带有障碍物的网格如果某些格子是障碍物金币数为负无穷或标记为不可通过那么在递推时对于障碍物格子其dp值可以设为一个极小值或者直接跳过该格子的计算意味着没有路径能到达该格子。在初始化第一行和第一列时也要特别注意一旦遇到一个障碍物它右边的所有格子对于第一行或下边的所有格子对于第一列都无法从起点直达了。变种3方向扩展如果移动方向增加到四个上、下、左、右问题就变成了在图上的最长路径问题。由于可能存在环绕圈子简单的DP就无法解决了需要用到图论中的最长路径算法或者如果所有权重为正这实际上变成了一个NP难问题在一般图中。这反衬出本题限制“只能向右或向下”的重要性——它保证了移动的“无后效性”和“无环性”这是能用DP求解的关键。变种4三维或更高维想象一个立方体你从一角出发每次只能向三个坐标轴正方向移动一个单位求最大总和。这就是三维DP状态定义为dp[x][y][z]转移方程类似。核心思想是一模一样的。思维扩展为什么DP能工作这道题能使用DP依赖于两个关键性质最优子结构一个问题的最优解包含其子问题的最优解。从(i,j)到终点的最优路径必然包含从它的下一个步骤(i1,j)或(i,j1)到终点的最优路径。如果子路径不是最优的那么总路径就可以通过替换成更优的子路径来变得更好这与“最优”矛盾。无后效性未来的决策只依赖于当前的状态位置(i,j)而不依赖于如何到达这个状态的历史路径。无论你是以何种方式走到(i,j)这个格子的从这个格子往后走的最大收益dp[i][j]都是确定的。这使得我们可以用dp[i][j]这个状态来概括所有到达(i,j)的历史信息。很多动态规划问题核心就是寻找正确的“状态定义”使得问题满足这两个性质。棋盘路径问题提供了一个近乎完美的可视化模型来理解这些概念。8. 蓝桥杯实战编码与调试要点最后我们落实到蓝桥杯OJ的代码实现上。以Python为例给出一个完整、健壮的AC代码并分享几个调试时容易踩的坑。def main(): import sys input sys.stdin.read data input().split() N int(data[0]) grid [] idx 1 for _ in range(N): row list(map(int, data[idx:idxN])) grid.append(row) idx N # 使用一维DP进行空间优化 dp [0] * N # 初始化第一行 dp[0] grid[0][0] for j in range(1, N): dp[j] dp[j-1] grid[0][j] # 递推后续行 for i in range(1, N): # 更新本行第一列 dp[0] dp[0] grid[i][0] for j in range(1, N): # dp[j] 在赋值前是上一行j列的值dp[j-1]是本行已更新的j-1列的值 dp[j] grid[i][j] max(dp[j], dp[j-1]) print(dp[N-1]) if __name__ __main__: main()踩坑点与调试心得输入格式处理蓝桥杯的题目经常是一次性给出所有输入。使用sys.stdin.read()一次性读取再按空格或换行分割是高效可靠的方法。务必先解析出N再根据N来读取N行N列的数据避免索引错乱。边界初始化这是DP最容易出错的地方。务必单独处理第一行和第一列。在一维DP的实现中dp[0] dp[0] grid[i][0]这行代码对应每一行第一列的更新千万不能漏掉也不能错误地放在内层循环之后。数组索引题目和代码中通常使用0-based索引从0开始。要清楚grid[i][j]对应的是棋盘的第i行、第j列从0数起。循环范围range(N)是[0, N-1]。空间与时间对于本题N最大一般不会超过1000O(N²)的时间约10^6次操作和O(N)的空间是完全可接受的。如果N更大比如10^4O(N²)的时间可能就会超时但这道题的数据范围通常设计在DP可解范围内。验证小数据在提交前一定要用一些小例子验证。比如N1棋盘只有一个数[[5]]答案应为5。N2棋盘[[1,2],[3,4]]路径 1-2-4 和 1-3-4 总和都是7。手动模拟一下DP表的填充过程确保和你的逻辑一致。这道“拿金币”就像动态规划领域的一把钥匙它简单到足以让你看清DP的所有核心部件状态定义、转移方程、边界处理、计算顺序、空间优化。吃透这一道题再去看背包问题、序列问题等你会发现它们的内核是相通的只是状态的定义和转移的方式变得更加抽象和多样。在练习时不妨尝试用三种方法暴力递归、记忆化搜索、递推DP都实现一遍感受它们之间的联系与演变这对建立扎实的DP思维至关重要。