动态规划路径类 DP 入门：3 道经典例题（最小路径和 + 迷雾森林 + 过河卒）全解析

文章目录

矩阵的最小路径和
迷雾森林
过河卒

路径类 dp 是线性 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>usingnamespace std;constint N =510;int n, m;int a[N][N], dp[N][N];intmain(){//处理输入 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;}

迷雾森林

题目描述

题目解析
1、状态表示
dp[i][j]表示从[m 1]格子走到[i j]格子时，一共有多少种方案。
2、状态转移方程
还是根据最后一步推导状态转移方程，因为题目规定只能向上或向右走，所以假设最后一个格子为[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

3、初始化

因为本题填表时会访问左边格子和下边格子，所以需要将dp数组第0列和第0行格子初始化为0，因为dp数组在全局开辟，所以值默认为0，不需要手动用memset初始化。
因为本题是求解方案数，后续格子方案数就是从第一个格子累加而来，所以将dp[m][1]初始化为1（注意：填表时不填[m][1]格子）
4、填表顺序
因为根据前面推导的状态转移方程填表时需要访问左边格子和下边格子，所以填表顺序是从下往上填每一行，填每一行时遵循从左往右。
5、输出结果
dp[1][n]

注意：本题规定答案需要对2333取模。
代码

#include<iostream>#include<stdio.h>usingnamespace std;constint N =3010;constint MOD =2333;int m, n;int a[N][N], dp[N][N];intmain(){//处理输入 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];return0;}

过河卒

题目描述

题目解析
由于本题强制规定从[0 0]格子开始填表，所以为了方便处理数组越界问题，我们将题目输入的B 点坐标和马的坐标统一加1，这样就相当于将整个棋盘往下和往右移了一格，就可以从[1 1]格子开始填表
1、状态表示
dp[i][j]表示从[1 1]格子走到[i j]格子时，一共有多少种方案。
2、状态转移方程
还是根据最后一步推导状态转移方程，题目规定卒行走的规则只能向下、或者向右，所以状态转移方程：
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
但是需要注意只有走到不是马的控制点时才能用状态转移方程填表，如果走到马的控制点不做任何操作，让它保持初始值0即可。
3、初始化
本题需要对a、dp数组分别初始化，dp数组将[1][1]置为1即可，因为方案数问题的答案需要从第一个格子开始累加得到。
a数组的处理思路是将马的9个控制点全部置为1，其余点保持0，在后面根据状态转移方程填表时需要判断a数组对应格子是否为0，如果为0可以填表，不为0则直接continue，不做任何操作。本题对a数组初始化我们借助方向向量实现。
4、填表顺序
从左往右，从上往下
5、输出结果
dp[n][m]

注意：
1、马所在的点也是马的控制点。
2、dp数组要用long long类型，因为方案数类型题目的数据是阶层级别的。

代码

#include<iostream>usingnamespace std;typedeflonglong LL;constint 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};intmain(){//处理输入 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;return0;}

以上就是小编分享的全部内容了，如果觉得不错还请留下免费的赞和收藏
如果有建议欢迎通过评论区或私信留言，感谢您的大力支持。
一键三连好运连连哦~~