正经题解｜最低通行费

【算法分析】

通过2N-1分析可以得到，商人不能走回头路，这样才能在n+n-1 =2n-1 个单位时间到达终点，所以和摘花生一样；
但是这里最终答案是求最小值，所以把第0行、第0列初始化为较大值，不能按0来算；然后发点左上角需要特判；

【参考代码】

#include<bits/stdc++.h>

using namespace std;

const int N = 110, INF = 1e9;

int n;
int a[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 >> a[i][j];
        }
    }
    //由于求最小，那就需要把第0行、第0列初始化为较大值
    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[i][j] = a[i][j];
            else
                f[i][j] = min(f[i - 1][j] + a[i][j], f[i][j - 1] + a[i][j]);
        }
    }
    cout << f[n][n];
    return 0;
}