第十四单元：动态规划 · 最优子结构与路径决策

封神冰川的最后一道试炼里,门卫要求你收集足够多的黄金才能通关。硬币一行行铺在唯一的出口通道上,你每往前走一行只能拾取一枚,而且只能选下一行里紧邻的左右两枚之一。一步走错,致命的光束就会将你烧成灰烬。要在"每步只有局部两个选择"的约束下,收集到全局最多的黄金——这正是计算机科学中一门威力强大的算法思想:动态规划(Dynamic Programming, DP)。这是本课程数据结构与算法之旅的压轴单元,也是你从"会写代码"迈向"会设计算法"的关键一跃。

14.1.1 什么是动态规划（What Is Dynamic Programming）

14.1.1.1 用子问题的解拼出大问题的解 Build the big answer from sub-answers

动态规划是一种把复杂问题拆成一系列重叠子问题、并复用子问题结果来求最优解的方法。它的精髓在于:不重复计算已经算过的子问题,而是把每个子问题的答案存起来(通常放在一张表里),后续直接查用。相比"暴力枚举所有路径"(路径数会指数级爆炸),DP 把工作量降到了可控的多项式级别。

14.1.2 最优子结构（Optimal Substructure）

14.1.2.1 大问题的最优解含子问题的最优解 The best overall solution contains best sub-solutions

动态规划能奏效,靠的是问题具备最优子结构:一条从某格出发的最优路径,必然由"这一格 + 它下面某个邻居出发的最优路径"构成。所以只要知道了"左下格"和"右下格"各自能拿到的最大值,当前格的最大值就等于自身价值 + 两者中的较大者。这个"局部最优拼出全局最优"的性质,正是我们敢于逐行递推的底气。

14.2.1 硬币地图（The Gold Map）

14.2.1.1 把散落的硬币装进网格 Place scattered coins into a grid

第一步是把游戏世界里散落的硬币,整理成一个整齐的二维数组(gold map):行代表第几排、列代表这一排的第几个位置,每个元素存该位置硬币的价值,没硬币的地方填 0。关卡用列表推导式先造出一张全 0 的模板,再把每枚硬币按坐标"归位"填进去。这种"先建表、再填值"的建模,是动态规划的起点。

# 先造一张全 0 的二维模板,再填入硬币价值
def makeGoldMap(coins):
    template = [[0 for j in range(2 * coinLines - 1)] for i in range(coinLines)]
    for coin in coins:
        row = int((coin.pos.y - zeroPoint.y) / distanceY)
        col = int((coin.pos.x - zeroPoint.x) / distanceX)
        template[row][col] = coin.value
    return template

14.2.2 坐标换算索引（Converting Coordinates to Indices）

14.2.2.1 从游戏坐标算出行列 Compute row/col from game coordinates

游戏里硬币有 pos.x、pos.y 的物理坐标,要把它们换算成数组的行、列索引。做法是:减去起点 zeroPoint、再除以行/列间距、取整。row = int((coin.pos.y - zeroPoint.y) / distanceY) 得到第几排,col 同理得到第几列。这套"物理坐标 → 逻辑索引"的换算,让算法能在干净的网格上思考,最后再换算回去移动英雄。

14.3.1 从底部逐行累计（Accumulate Row by Row from the Bottom）

14.3.1.1 为什么从最后一行往上算 Why compute from the last row upward

动态规划的核心步骤是递推。这里我们采用自底向上(bottom-up):最后一行本身就是"从该格出发能拿到的最大值"(因为下面没有格子了),把它当作基础;然后倒数第二行的每个格子,加上它左下/右下中较大的那个已算好的值;如此一行行往上,直到第一行。每个格子最终存的,就是"从此格出发,一路向下能收集到的黄金最大总和"。

14.3.2 倒序遍历（Iterating in Reverse）

14.3.2.1 用 range 从倒数第二行走到第 0 行 Use range to loop from the second-to-last row to row 0

"自底向上"在代码里就是倒序遍历行。最后一行是基础不用动,从倒数第二行(索引 len - 2)开始,一直递推到第 0 行(索引 0)。Python 用 range(len(goldMap) - 2, -1, -1) 实现这个"从大到小、步长 -1"的倒序循环。方向对了,才能保证每次用到的"下一行"都是已经算好的。

# 倒序遍历:从倒数第二行递推到第 0 行
for i in range(len(goldMap) - 2, -1, -1):
    line = goldMap[i]
    for j in range(len(line)):
        if line[j] == 0:
            continue          # 空位跳过,不是硬币
        # … 在这里做状态转移(见 14.4)…

14.4.1 取左下右下较大者（Take the Larger of Down-Left and Down-Right）

14.4.1.1 动态规划的灵魂公式 The soul of dynamic programming

状态转移方程是动态规划的灵魂——它描述"当前状态的值,如何由更小的子状态推出"。本关的方程很简洁:当前格的累计值 = 自身价值 + max(左下格累计值, 右下格累计值)。因为从当前格只能走向左下或右下,自然要选那个"后续收益更大"的方向。用 max() 一步选出较大者,累加上去即可。

# 状态转移:当前格 += 左下、右下中较大者
goldMap[i][j] += max(goldMap[i + 1][j - 1], goldMap[i + 1][j + 1])
#            自身已含 ↑            左下(i+1,j-1)          右下(i+1,j+1)

14.4.2 边界处理（Handling the Edges）

14.4.2.1 最左列没有左下、最右列没有右下 The leftmost column has no down-left; the rightmost has no down-right

方程在网格边缘要特殊处理:最左列(j == 0)没有左下邻居,只能选右下;最右列(j == len - 1)没有右下邻居,只能选左下;中间的格子才用 max() 二选一。这三种情况用 if / elif / else 分开处理,避免访问到不存在的邻居而取错值或越界。

# 边界分情况:最左只能右下,最右只能左下,中间取较大
if j == 0:
    goldMap[i][j] += goldMap[i + 1][j + 1]   # 只有右下
elif j == len(line) - 1:
    goldMap[i][j] += goldMap[i + 1][j - 1]   # 只有左下
else:
    goldMap[i][j] += max(goldMap[i + 1][j - 1], goldMap[i + 1][j + 1])

14.5.1 选最优起点（Choose the Best Starting Column）

14.5.1.1 第一行里累计值最大的那一列 The column in row 0 with the largest accumulated value

递推完成后,第一行(第 0 行)每个格子的值,就是"从该格起步能收集到的黄金总和"。要拿最多黄金,只需在第一行里找出值最大的那一列作为起点。遍历第 0 行,用一个"擂台"变量记录当前最大值和对应列号,一遍扫下来就得到最优起点 bestCol。

# 在第 0 行找累计值最大的列 = 最优起点
def chooseStartCol(goldMap):
    bestCol = 0
    bestValue = 0
    for i in range(len(goldMap[0])):
        if goldMap[0][i] > bestValue:
            bestValue = goldMap[0][i]
            bestCol = i
    return bestCol

14.5.2 记录左右方向（Recording Left/Right Choices）

14.5.2.1 从起点再走一遍，逐行决定方向 Walk down from the start, deciding direction each row

知道起点和每格的最大值后,还要回溯出具体的行走路径。从起点列开始,逐行向下:比较当前格的左下和右下哪个累计值更大,就往哪边走,并把这一步记为 "L"(左)或 "R"(右),同时更新列号。边界列则只能朝唯一可行的方向走。这样得到一个方向序列 path,就是英雄该走的完整路线。

# 从起点逐行回溯,记录每步是往左(L)还是往右(R)
def findPath(goldMap, col):
    path = []
    for i in range(len(goldMap) - 1):
        if col == 0:                 # 最左列只能向右
            path.append("R")
            col += 1
        elif col == len(goldMap[i]) - 1:   # 最右列只能向左
            path.append("L")
            col -= 1
        elif goldMap[i + 1][col - 1] < goldMap[i + 1][col + 1]:
            path.append("R")       # 右下更大,向右
            col += 1
        else:
            path.append("L")       # 否则向左
            col -= 1
    return path

14.6.1 按方向前进（Advance by Direction）

14.6.1.1 把 L/R 序列翻译成移动指令 Translate the L/R sequence into moves

最后,把起点列换算回游戏 X 坐标先走到起点,再遍历 path 序列:遇到 "L" 就向左下方移动一格(x - distanceX, y + distanceY),遇到 "R" 就向右下方移动一格(x + distanceX, y + distanceY)。每一步都精准落在下一枚硬币上,既收集了黄金,又避开了致命光束。这一步把"逻辑上的路径"变成了"世界里的行动"。

# 沿路径移动:L 向左下, R 向右下
for p in route:
    if p == "L":
        hero.moveXY(hero.pos.x - distanceX, hero.pos.y + distanceY)
    else:
        hero.moveXY(hero.pos.x + distanceX, hero.pos.y + distanceY)

这一节聚焦关卡的策略、思路与算法设计,只展示用于说明的关键片段,完整通关程序请你自己动手完成。

第 31 关 · 黄金选择

🪙 黄金选择 —— 动态规划求最大黄金路径

图2：黄金选择——硬币交错铺在通道上,每行只能取一枚且只能选左下/右下;用动态规划算出黄金最多的路径并沿之前进

策略:建表 → 递推 → 选起点 → 回溯 → 移动

门卫要求收集足够黄金,你沿唯一出口方向前进,每行取一枚硬币,只能选下一行紧邻的左下或右下之一,走错就被光束烧毁。这是典型的网格最大路径和问题,标准动态规划五步走:① 把硬币建成二维地图;② 自底向上递推每格最大累计值;③ 在顶行选最优起点;④ 回溯出左右方向序列;⑤ 按序列移动英雄。

思路拆解一:递推每格的最大累计值

processMap 倒序遍历行(从倒数第二行到第 0 行),对每个硬币格套用状态转移:边界列只能朝唯一方向累加,中间列用 max() 取左下右下较大者。空位(值为 0)直接 continue 跳过。递推完,顶行每格就存着"从此起步的黄金总和"。

# 关键片段:自底向上递推(核心)
for i in range(len(goldMap) - 2, -1, -1):
    line = goldMap[i]
    for j in range(len(line)):
        if line[j] == 0:
            continue
        if j == 0:
            goldMap[i][j] += goldMap[i + 1][j + 1]
        elif j == len(line) - 1:
            goldMap[i][j] += goldMap[i + 1][j - 1]
        else:
            goldMap[i][j] += max(goldMap[i + 1][j - 1], goldMap[i + 1][j + 1])

思路拆解二:选起点并回溯路径

用 chooseStartCol 在顶行找出累计值最大的列作为 startColumn;再用 findPath 从这一列逐行向下,比较左下右下、记录 "L"/"R"。注意回溯时用的比较逻辑要与递推时的选择保持一致,才能沿着当初算出的最优路径行走。

# 关键片段:选起点 + 回溯 + 走到起点
processedMap = processMap(myMap)
startColumn = chooseStartCol(processedMap)
hero.moveXY(startColumn * distanceX + zeroPoint["x"], hero.pos.y)
route = findPath(processedMap, startColumn)   # 得到 L/R 方向序列

为什么不暴力枚举：若硬币有 10 行、每步 2 选 1,路径总数高达 2⁹ = 512 条,行数再多会指数爆炸。动态规划把每个格子的最优值只算一次并存起来复用,总工作量只与格子数成正比。这就是 DP 相比暴力搜索的核心威力——用空间(那张表)换时间。

精准踩点,一步都不能错：关卡强调"准确地移动到下一枚硬币上,一个错误的步骤会被光束烧毁"。所以坐标换算(col * distanceX + zeroPoint["x"])和每步 distanceX / distanceY 的位移必须精确;逻辑索引与物理坐标要严格对齐,算法算得再对,走偏一格也会失败。

14.8.1 新手最容易踩的坑（Pitfalls for Beginners）

14.8.1.1 动态规划的典型问题 Typical issues with dynamic programming

图3：递推方向反了、漏了边界、回溯与递推逻辑不一致、坐标换算出错,是本单元最常见的失误