C++---线性dp---最低通行费（每日一道算法2023.1.14）

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

题目
一个商人穿过一个 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

#include <iostream>
#include <cstring>

using namespace std;
const int N = 110;
int n;
int a[N][N], f[N][N];

int main()
{
    //读入
    cin >> n;
    for (int i = 1; i<=n; i++) {
        for (int j = 1; j<=n; j++) cin >> a[i][j];
    }

    //初始化DP数组f,使每个元素为最大值,以便后面的计算时比较得出较小的费用
    for (int i = 0; i<=n; i++) memset(f[i], 0x3f3f3f3f, sizeof f[i]);  
    
    //线性DP
    for (int i = 1; i<=n; i++) {
        for (int j = 1; j<=n; j++) {
            if (i == 1 && j == 1) f[1][1] = a[1][1];  //第一个点的费用赋值
            else {
                //如果i>1,则可以从上面走过来,比较上面的路径费用和当前路径费用的大小,并取较小值
                if (i > 1) f[i][j] = min(f[i-1][j] + a[i][j], f[i][j]);
                //如果j>1,则可以从左面走过来,比较左面的路径费用和当前路径费用的大小,并取较小值
                if (j > 1) f[i][j] = min(f[i][j-1] + a[i][j], f[i][j]);
            }
        }
    }

    cout << f[n][n] << endl;  //输出最小费用
    return 0;
}