多维动态规划：用表格解决复杂问题

多维动态规划：用表格理清复杂问题

想象你在玩一个平面拼图，每个格子都有分数，从左上角走到右下角，每次只能向右或向下走，怎么走才能让总分最高？如果问题变成了立体魔方，你不仅要考虑平面位置，还要考虑层数或者剩余步数，这时就需要用多维动态规划来帮我们系统地填表格找最优解。

简单来说，多维动态规划就是把动态规划的状态从一维数组扩展到二维、三维甚至更高维度的数组，让每一个格子（或每个维度组合）都代表一个子问题的最优值。就像在一个多层抽屉的衣柜里找衣服，我们需要同时知道抽屉的层数和位置才能确定是哪一件。在编程中，我们常用 dp[i][j] 表示在位置 (i,j) 时的最优结果，dp[i][j][k] 表示三个维度下的结果。

核心步骤：状态、转移、边界

1. 状态定义 —— 明确每个格子代表什么

状态是动态规划的“灵魂”。在多维DP中，我们通常用数组的下标表示问题的不同维度，数组的值表示该状态下的最优值（或方案数、可行性等）。

生活例子：
你要从学校（左上角）走到家（右下角），路上每个路口可能捡到不同数量的零食。你每次只能向右或向下走一步。问最多能捡到多少零食？
我们可以定义 dp[i][j] 表示走到第 i 行第 j 列的路口时，已经捡到的零食总数最大值。这里的 i 和 j 就是两个维度（行和列）。

C++ 代码片段：

int m = 3, n = 4;               // 行数、列数
int snack[3][4] = {             // 每个路口的零食数
    {2, 5, 1, 3},
    {8, 0, 4, 6},
    {1, 9, 7, 2}
};
int dp[3][4] = {0};             // dp[i][j] 记录走到(i,j)的最大零食数

2. 状态转移方程 —— 怎样从一个格子走到下一个格子

有了状态，我们需要知道如何从已知的格子推出未知的格子。一般根据问题的移动规则来写方程。

常见的二维转移模式：

只能向右或向下：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + 当前格子的值
只能向右、向下、向右下：dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 当前值
求路径总数：dp[i][j] = dp[i-1][j] + dp[i][j-1]（前提是格子可通行）

继续零食例子：
因为只能向右或向下，所以走到 (i,j) 的前一步要么是从上面来 (i-1,j)，要么是从左边来 (i,j-1)。我们选较大的那个，再加上当前格子的零食数：

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + snack[i][j];

3. 边界初始化 —— 先填好第一行和第一列

边界就是那些没有“上面”或“左边”的格子。对于第一行（i=0），只能从左边来，所以 dp[0][j] = dp[0][j-1] + snack[0][j]。对于第一列（j=0），只能从上面来，所以 dp[i][0] = dp[i-1][0] + snack[i][0]。起点 (0,0) 直接等于零食数。

代码片段：

dp[0][0] = snack[0][0];                     // 起点
for (int j = 1; j < n; j++)                 // 初始化第一行
    dp[0][j] = dp[0][j-1] + snack[0][j];
for (int i = 1; i < m; i++)                 // 初始化第一列
    dp[i][0] = dp[i-1][0] + snack[i][0];

为什么需要初始化？
因为动态规划是从小问题向大问题递推的，边界是最小的子问题，不初始化就无法继续填表。

新手容易犯的常见错误

忘记初始化边界
直接跳进双重循环，导致 dp[0][1] 使用未定义的 dp[0][0] 值（如果数组未清零可能得到随机数）。
✅ 先手动给边界赋值，再写转移循环。
混淆行和列的下标顺序
在二维数组中，通常第一个下标是行（i），第二个是列（j）。转移时 dp[i-1][j] 表示上一行同列，dp[i][j-1] 表示同一行的前一列，别搞反了。
✅ 写代码时可以用 row 和 col 作为变量名，或者写清楚注释。
没有考虑障碍物或不可走格子
如果有些格子不能走，转移时要加上 if 判断，跳过不可达的格子，或者给阻碍格设一个极小值（如 -1e9）。
忘记处理越界
比如三维 DP 中，某一维度的索引可能为负数，需要谨慎处理边界条件。
状态定义不清晰，导致维度过多或过少
比如问题中除了位置还有“已走步数限制”，就应增加一维表示剩余步数。如果遗漏，结果可能错误。

完整可运行示例：最大零食收集

下面是一段完整的 C++ 代码，包含手动输入和结果输出，并增加了详细注释。你可以直接复制后运行测试。

#include <iostream>
#include <algorithm>   // 使用 max 函数
using namespace std;

int main() {
    // 输入地图大小
    int rows = 3, cols = 4;                     // 行数、列数
    int snack[3][4] = {                         // 每个格子的零食数
        {2, 5, 1, 3},
        {8, 0, 4, 6},
        {1, 9, 7, 2}
    };

    // 定义 dp 数组，并初始化为 0
    int dp[3][4] = {0};
    // 1. 边界初始化
    dp[0][0] = snack[0][0];                     // 起点
    for (int j = 1; j < cols; j++)              // 第一行：只能从左过来
        dp[0][j] = dp[0][j-1] + snack[0][j];
    for (int i = 1; i < rows; i++)              // 第一列：只能从上面过来
        dp[i][0] = dp[i-1][0] + snack[i][0];

    // 2. 填表：从 (1,1) 开始，逐行扫描
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            // 状态转移：取左边或上边较大值，加上当前零食
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + snack[i][j];
        }
    }

    // 输出结果
    cout << "最多能捡到 " << dp[rows-1][cols-1] << " 个零食" << endl;
    return 0;
}

运行结果：
最多能捡到 29 个零食（路径示例：2→5→1→4→7→2 等等，需自行检验）。