C++算法
动态规划路径类 DP 入门：最小路径和、迷雾森林与过河卒
路径类动态规划基于矩阵行走规则求解方案数或最值。解析矩阵最小路径和、迷雾森林及过河卒三道经典例题，阐述状态定义、转移方程、初始化策略及填表顺序，提供 C++ 代码实现，辅助理解动态规划在路径问题中的应用。
路径类动态规划基于矩阵行走规则求解方案数或最值。解析矩阵最小路径和、迷雾森林及过河卒三道经典例题，阐述状态定义、转移方程、初始化策略及填表顺序，提供 C++ 代码实现，辅助理解动态规划在路径问题中的应用。
路径类 DP 是线性 DP 的一种，它是在一个 n × m 的矩阵中设置一个行走规则，研究从起点走到终点的方案数、最小路径和或者最大路径和等问题。
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
状态表示 dp[i][j] 表示从 [1, 1] 格子走到 [i, j] 格子时，所有方案下的最小路径和。
状态转移方程 以最后一步推导，走到最后一个格子 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]
初始化 因为本题填格子时需要访问左边和上边格子，所以需要处理边界情况。在填第一行和第一列格子时会访问到第 0 行和第 0 列，但是第 0 行和第 0 列是无意义的，所以我们需要把第 0 行和第 0 列初始化为无穷大。当填表访问到第 0 行或第 0 列格子时由于状态转移方程是取两个格子较小值，所以永远不会取到第 0 行或第 0 列格子。 还需要将 dp[1][1] 初始化为 a[1][1]，因为 [1, 1] 的最小路径和就是它本身，并且注意在填表时跳过 [1, 1] 格子。
填表顺序 从上往下，从左往右。
输出结果 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 = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
// 初始化
memset(dp, 0x3f3f3f3f, sizeof(dp));
dp[1][1] = a[1][1];
// 依序填表
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == 1 && j == 1) continue;
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
}
}
// 输出结果
cout << dp[n][m] << endl;
return 0;
}
在一个 n * m 的迷宫中，有些位置有树不能走，求从起点到终点的路径方案数。
状态表示 dp[i][j] 表示从 [m, 1] 格子走到 [i, j] 格子时，一共有多少种方案。
状态转移方程 根据最后一步推导，只能向上或向右走。假设最后一个格子为 [i, j]，那么上一个格子可能是 [i, j - 1] 或者 [i + 1, j]。 格子 [i, j] 的方案数就是 [i, j - 1] 格子方案数加上 [i + 1, j] 格子方案数。 需要注意，本题只能走空地，如果遇到树是不能走的，也就是只有空地可以用状态转移方程填表，森林格子还是保持默认初始值 0。 状态转移方程为： a[i][j] = 0 --> dp[i][j] = dp[i][j - 1] + dp[i + 1][j] a[i][j] = 1 --> dp[i][j] = 0
初始化
填表顺序 从下往上填每一行，填每一行时遵循从左往右。
输出结果 dp[1][n]
注意：本题规定答案需要对 2333 取模。
#include <iostream>
#include <stdio.h>
using namespace std;
const int N = 3010;
const int MOD = 2333;
int m, n;
int a[N][N], dp[N][N];
int main() {
// 处理输入
cin >> m >> n;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
}
}
// 初始化
dp[m][1] = 1;
// 按序填表
for (int i = m; i >= 1; i--) {
for (int j = 1; j <= n; j++) {
// [m][1] 格子以及初始化，无需再次填
if (i == m && j == 1) continue;
if (a[i][j] == 0) dp[i][j] = (dp[i][j - 1] + dp[i + 1][j]) % MOD;
}
}
// 输出结果
cout << dp[1][n];
return 0;
}
棋盘上有 A 点 (0, 0) 和 B 点 (n, m)，有一个马位于 (c, d)。卒只能向下或向右走，且不能经过马的控制点，求从 A 到 B 的路径方案数。
由于本题强制规定从 [0, 0] 格子开始填表，为了方便处理数组越界问题，我们将题目输入的 B 点坐标和马的坐标统一加 1，这样就相当于将整个棋盘往下和往右移了一格，就可以从 [1, 1] 格子开始填表。
状态表示 dp[i][j] 表示从 [1, 1] 格子走到 [i, j] 格子时，一共有多少种方案。
状态转移方程 题目规定卒行走的规则只能向下、或者向右，所以状态转移方程： dp[i][j] = dp[i][j - 1] + dp[i - 1][j] 需要注意只有走到不是马的控制点时才能用状态转移方程填表，如果走到马的控制点不做任何操作，让它保持初始值 0 即可。
初始化 本题需要对 a、dp 数组分别初始化。
填表顺序 从左往右，从上往下。
输出结果 dp[n][m]
注意：
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 25;
int n, m, c, d;
int a[N][N];
LL dp[N][N];
// 方向向量
int dx[8] = {2, 2, 1, 1, -1, -1, -2, -2};
int dy[8] = {1, -1, 2, -2, 2, -2, 1, -1};
int main() {
// 处理输入
cin >> n >> m >> c >> d;
n++, m++, c++, d++;
// 初始化
dp[1][1] = 1;
for (int i = 0; i < 8; i++) {
a[c + dx[i]][d + dy[i]] = 1;
}
a[c][d] = 1;
// 按序填表
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == 1 && j == 1) continue;
if (a[i][j] == 0) dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
// 输出结果
cout << dp[n][m] << endl;
return 0;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online