动态规划DP 数字三角型模型 最低通行费用（题目详解+C++代码完整实现）

最低通行费用

原题链接

AcWing 1018. 最低同行费用

题目描述

一个商人穿过一个 N×N的正方形的网格，去参加一个非常重要的商务活动。
他要从网格的左上角进，右下角出。每穿越中间 1个小方格，都要花费 1个单位时间。商人必须在 (2N−1)个单位时间穿越出去。
而在经过中间的每个小方格时，都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用？
注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。

输入格式
第一行是一个整数，表示正方形的宽度 N。后面 N行，每行 N个不大于 100的正整数，为网格上每个小方格的费用。
输出格式
输出一个整数，表示至少需要的费用。

数据范围
1≤N≤100

输入样例：

5
1  4  6  8  10
2  5  7  15 17
6  8  9  18 20
10 11 12 19 21
20 23 25 29 33

输出样例：

109

样例解释
样例中，最小值为 109=1+2+5+7+9+12+19+21+33。

题目分析

“商人必须在 (2N−1)个单位时间穿越出去” 意味着不能走回头路，
因此，该题转化为 “ 摘花生 ”。

不同点在于，该题 “最低通行费” 所求为最小值（min），而 “摘花生” 所求为最大值（max）。

全局变量的初值默认为0，最小值（min）在求解过程中可能涉及到初始化问题，因为0可以是最小值，而边界情况又是不合理的，需要我们多加处理。

数据的初始化处理

第一列 （i，1）：
路径不可能来自第一列的左侧，f[i][0] 初始化为INF。
第一行（1，j）：
路径不可能来自第一行的上侧，f[0][j] 初始化为INF。

同时，在状态计算的过程当中，路径一定过起点（1，1），因此，f[1][1]的状态值不由f[0][1]或者f[1][0]得到，而是直接赋值为 w[1][1]。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
const int INF=2e9;
int n;
int w[N][N];  //费用
int f[N][N];  //状态表示
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&w[i][j]);}}//初始化处理for(int i=1;i<=n;i++){f[i][0]=INF;  //第一列的左侧f[0][i]=INF;  //第一行的上侧}//状态计算for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==1&&j==1) f[1][1]=w[1][1];  //如果是起始点(1,1)，则直接赋值w[1][1]else f[i][j]=min(f[i-1][j],f[i][j-1])+w[i][j];  //否则通过状态计算}}printf("%d",f[n][n]);  //右下角终点(n,n)的f状态值即为最终答案return 0;
}