1018. 最低通行费

题目传送门

一、题目大意

从左上角进去，从右下角出来，每穿过一个小方格，就要消耗一单位的时间。
商人必须要在\(2*n-1\)的时间内，穿到右下角去。每经过一个小方格，都需要缴纳一定的费用，问我们总花费最小是多少？

二、题目分析

摘花生的题与这道题特别相似，摘花生是从左上走到右下角，只能是向下或者向右走，不能回头走,问我们摘到的最大值是多少？

这道题要求在\(2*n-1\)的时间内，从左上角走到右下角，最小花费是多少？

理解一下这个\(2*n-1\)，如果我们不走回头路的话，那么需要走\(2*n-1\)步，所以消耗的时间为\(2*n-1\)单位时间。

换句话说，就是只能向右或向下走，不能向左或向上，否则不能在\(2*n-1\)步中走到右下角。

分析完\(2*n-1\)，就明白这道题其实就是摘花生那道题，只不过不是求最大值，而是求最小值即可。

线性结构就是\(f[i]\),网络图就是\(f[i][j]\),如果是背包问题，那么第一维是物品，第二维是体积。

三、特别之处

1、注意边界

每一个位置，都可以从它的正上方或者左前方过来，但第一行不能从上一行过来，第一列不能从上一列过来，需要特殊处理。

2、最小值需要注意初始化

数组声明在全局区，默认值是\(0\),而求最小值，而可能把\(0\)认为小于已经取得的最小值，导致最终结果为\(0\)的错误，所以，需要对数据进行最大化的初始化,预求最小，先设最大！

四、实现代码

#include 

using namespace std;

const int N = 110;
const int INF = 0x3f3f3f3f;
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];

    //初始化第一行,因为第一行的每个位置，只能从左侧过来，所以有下面的递推式。
    for (int i = 1; i <= n; i++)f[1][i] = f[1][i - 1] + w[1][i];

    //初始化第一列,因为第一列的每个位置，只能从上侧过来，所以有下面的递推式。
    for (int i = 1; i <= n; i++)f[i][1] = f[i - 1][1] + w[i][1];

    //第一行第一列讨论完，剩下的可以愉快的递推了~
    for (int i = 2; i <= n; i++)
        for (int j = 2; j <= n; j++) {
            //初始化数据，预求最小，先设最大
            f[i][j] = INF;
            f[i][j] = min(f[i][j - 1], f[i - 1][j]) + w[i][j];
        }
    //输出大吉
    printf("%d \n", f[n][n]);
    return 0;
}