路径类 DP 本质上是线性 DP 的一种变体,核心在于在 n × m 的矩阵中设定行走规则,求解从起点到终点的最优方案数或路径和。入门阶段的《数字三角形》其实就是这类问题的基础。
矩阵的最小路径和
题目要求在一个 n × m 的矩阵中,从左上角走到右下角,求路径上数字之和的最小值。
状态定义
设 dp[i][j] 表示从起点 [1, 1] 走到格子 [i, j] 时的最小路径和。
状态转移
考虑最后一步,到达 [i, j] 只能从上方 [i-1, j] 或左方 [i, j-1] 过来。因此状态转移方程为:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j]
初始化与边界
由于填表时需要访问左边和上边的格子,为了避免数组越界,我们将第 0 行和第 0 列初始化为无穷大。这样在取最小值时,永远不会选中这些无效位置。同时,将起点 dp[1][1] 初始化为 a[1][1],并在循环中跳过该点,防止被覆盖。
填表顺序 从上往下,从左往右依次计算。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int n, m;
int a[N][N], dp[N][N];
int main() {
// 输入矩阵
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
// 初始化 dp 数组为无穷大
memset(dp, 0x3f3f3f3f, sizeof(dp));
dp[1][1] = a[1][1];
// 依序填表
for (int i = 1; i <= n; i++) {
( j = ; j <= m; j++) {
(i == && j == ) ;
dp[i][j] = (dp[i - ][j], dp[i][j - ]) + a[i][j];
}
}
cout << dp[n][m] << endl;
;
}


