路径类动态规划入门：最小路径和、迷雾森林及过河卒

路径类动态规划是线性 DP 的一种，它是在一个 n × m 的矩阵中设置一个行走规则，研究从起点走到终点的方案数、最小路径和或者最大路径和等问题。入门阶段的《数字三角形》其实就是路径类 DP。

矩阵的最小路径和

题目描述

题目解析

1. 状态表示

dp[i][j] 表示从 [1, 1] 格子走到 [i, j] 格子时，所有方案下的最小路径和。

2. 状态转移方程

我们还是以最后一步来推导状态转移方程，走到最后一个格子 dp[n][m] 有两种情况，分别是从 dp[n - 1][m] 到 dp[n][m] 和从 dp[n][m - 1] 到 dp[n][m]，所以 dp[n][m] 的取值就是取 dp[n - 1][m] 和 dp[n][m - 1] 的较小值加 a[n][m]，所以状态转移方程如下： dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j]

3. 初始化

因为本题填格子时需要访问左边和上边格子，所以我们需要处理边界情况，在填第一行和第一列格子时会访问到第 0 行和第 0 列，但是第 0 行和第 0 列是无意义的，所以我们需要把第 0 行和第 0 列初始化为无穷大，当填表访问到第 0 行或第 0 列格子时由于状态转移方程是取两个格子较小值，所以永远不会取到第 0 行或第 0 列格子。

还需要将 dp[1][1] 初始化为 a[1][1]，因为 [1, 1] 的最小路径和就是它本身，并且注意在填表时跳过 [1, 1] 格子，首先因为已经将 [1, 1] 格子初始化过了，第二如果把状态转移方程用于 [1, 1] 格子，会把 [1, 1] 格子填为无穷大。

4. 填表顺序

从上往下，从左往右

5. 输出结果

dp[n][m]

代码

#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 = ; i <= n; i++) {
         ( j = ; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    
    (dp, , (dp));
    dp[][] = a[][];
    
     ( i = ; 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;
}