二维 DP = 填一张格子表：每个格子的答案 = 上面格子 + 左边格子（只能向右、向下走时）。记住「转移方程」，DP 就是「按行机械填表」——填到最后一个格子，答案就出来了。
想象你站在格子地图的左上角，只能向右或向下走，想知道到右下角一共有多少条不同的路线。笨办法是把每条路线都画出来——4×4 的地图就已经有 20 条，地图再大就画不动了。DP 的办法是填一张小表：到达任何一个格子的路线数 = 到达它上面格子的路线数 + 到达它左边格子的路线数（因为只能从这两个方向走进来）。于是第一行、第一列都只能走一条路，填 1；然后一行一行、从左到右往下加——填到右下角，答案就在那里。这种「用已经算好的格子，推出当前格子」的公式叫转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]。这里的 dp 是一张二维表（行、列对应地图的行、列），所以叫「二维 DP」。以后学 LIS、LCS、背包，全都是「换个地图，同一个填表动作」。
dp[i][j] = dp[i-1][j] + dp[i][j-1]，会手填 3×3 的表。// 为什么是「上面 + 左边」？ 你只能向右或向下走。要走进格子 (i,j)， 最后一步【只能】从两个地方跨进来： · 上面的格子 (i-1,j) —— 向下跨一步 · 左边的格子 (i,j-1) —— 向右跨一步 所以：到 (i,j) 的路线数 = 到 (i-1,j) 的路线数 + 到 (i,j-1) 的路线数 // 转移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1] // 边界：第一行、第一列 = 1 到第一行任意格子：只能一直向右 → 恰好 1 条路 到第一列任意格子：只能一直向下 → 恰好 1 条路 // 手填 3×3（按行、从左到右） 第1列 第2列 第3列 第1行: 1 1 1 第2行: 1 2 3 dp[2][3] = dp[1][3] + dp[2][2] = 1 + 2 = 3 第3行: 1 3 6 dp[3][3] = dp[2][3] + dp[3][2] = 3 + 3 = 6 // 答案：3×3 格子，左上到右下 = 6 条路
// 4×4 全表（边界 = 1，内部 = 上面 + 左边） 第1列 第2列 第3列 第4列 第1行: 1 1 1 1 第2行: 1 2 3 4 第3行: 1 3 6 10 第4行: 1 4 10 20 ← 答案 dp[4][4] // 抽一格验算：dp[4][4] = dp[3][4] + dp[4][3] = 10 + 10 = 20 ✓ // 组合数交叉验证（另一条思路） 从 (1,1) 到 (4,4)：要向下 (4-1) = 3 步，向右 (4-1) = 3 步，共 6 步。 每一步的「顺序」唯一决定一条路线，所以 路线数 = 在 6 步里选哪 3 步向下 = C(6,3) = 6! / (3! · 3!) = (6×5×4) / (3×2×1) = 20 ✓ 与填表结果一致
// 障碍在 (2,2)：路线不能踩这个格子 方法：填表遇到障碍格，直接写 0，后面照常算。 第1列 第2列 第3列 第4列 第1行: 1 1 1 1 第2行: 1 0* 1 2 ← (2,2) 是障碍，填 0 第3行: 1 1 2 4 第4行: 1 2 4 8 ← 答案 dp[4][4] = 8 // 关键格验算 dp[2][3] = dp[1][3] + dp[2][2] = 1 + 0 = 1 // 上面的路被障碍「掐断」，只剩左边 dp[3][2] = dp[2][2] + dp[3][1] = 0 + 1 = 1 dp[3][3] = dp[2][3] + dp[3][2] = 1 + 1 = 2 dp[4][4] = dp[3][4] + dp[4][3] = 4 + 4 = 8 ✓ // 对比：没有障碍时 dp[4][4] = 20 // 一个障碍，路线从 20 条掉到 8 条——堵在路口正中，影响巨大
dp[i][j] = min(上面, 左边) + cost[i][j]，会手填 4×4 花费表（答案 10）。// 花费地图（踩每个格子要付的费）： 第1列 第2列 第3列 第4列 第1行: 1 3 1 2 第2行: 2 1 4 1 第3行: 1 2 1 3 第4行: 3 1 2 1 // 转移方程变了：不再「相加」，而是「选便宜的一边」 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + cost[i][j] 边界：dp[1][1] = cost[1][1] = 1（起点的花费也要付） // 手填花费 DP 表（每格 = min(上, 左) + 本格花费）： 第1列 第2列 第3列 第4列 第1行: 1 4 5 7 只能从左边来：1+3, 4+1, 5+2 第2行: 3 4 8 8 dp[2][2] = min(4,3)+1 = 4 第3行: 4 6 7 10 dp[3][3] = min(8,6)+1 = 7 第4行: 7 7 9 10 ← 最小花费 = 10 // 验算 dp[4][4] = min(dp[3][4], dp[4][3]) + cost[4][4] // = min(10, 9) + 1 = 9 + 1 = 10 ✓
// 题目：4×4 花费地图，从 (1,1) 走到 (4,4)，只能向右/向下， // 求最小花费（每个格子踩上去都要付 cost）。 // 方法：dp[i][j] = min(上面, 左边) + cost[i][j]，逐行填表。 #include <iostream> #include <algorithm> using namespace std; const int N = 4; int cost[N+1][N+1] = { {0, 0, 0, 0, 0 }, {0, 1, 3, 1, 2 }, {0, 2, 1, 4, 1 }, {0, 1, 2, 1, 3 }, {0, 3, 1, 2, 1 } }; int main() { int dp[N+1][N+1] = {}; dp[1][1] = cost[1][1]; // 边界：起点的花费也要付 for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (i == 1 && j == 1) continue; int fromTop = (i > 1) ? dp[i-1][j] : 1e9; // 第 1 行没有「上面」 int fromLeft = (j > 1) ? dp[i][j-1] : 1e9; // 第 1 列没有「左边」 dp[i][j] = min(fromTop, fromLeft) + cost[i][j]; } } // 打印 dp 表 for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) cout << dp[i][j] << " "; cout << endl; } cout << "最小花费 = " << dp[N][N] << endl; return 0; } // 运行结果： // 1 4 5 7 // 3 4 8 8 // 4 6 7 10 // 7 7 9 10 // 最小花费 = 10 // 改成「数路」只需两步：dp[1][1] = 1；dp[i][j] = fromTop + fromLeft（相加）。