AcWing 1018. 最低通行费（线性DP）

题目链接

题目描述

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

题目模型

• 子题目：摘花生
• 因为要在（2N-1）个单位时间穿越出去，而从（1，1）走到（n，n）正好需要（2N-1）个单位时间，所以不能走回头路。

题目代码

#include 
#include 
#include 

using namespace std;

const int N = 110;

int n;
int w[N][N];
int f[N][N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
            cin >> w[i][j];
    
    memset(f, 0x3f, sizeof f);  //因为求min，所以初始化为最大，并且需要考虑边界问题
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
        {
            if(i == 1 && j == 1) f[i][j] = w[i][j];  //(1，1)需在循环内特判，否则会出错
            else f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j];
        }
           

    cout << f[n][n] << endl;
    
    return 0;
}