最低通行费

由题意可得：第一行所有点只能一直左走走到，所以f[i][j] = a[i][j] + f[i][j-1]， 同理第一列的点也只能一直向下走走到，f[i][j] = a[i][j] + f[i-1][j] 。
预处理完后，余下所有点到达该点的最小费用都等于min(到左边的点的最小费用， 到上面的点的最小费用)+该点的费用。

状态转移方程：f[i][j] = min(f[i-1][j], f[i][j-1]) + a[i][j]

#include <iostream>
#include <cstdio>
using namespace std;
//Mystery_Sky
//
#define M 101
int f[M][M], a[M][M], n;
int ans;
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
            if(i == 1) f[i][j] = a[i][j] + f[i][j-1];
            if(j == 1) f[i][j] = a[i][j] + f[i-1][j];
        }
    for(int i = 2; i <= n; i++)
        for(int j = 2; j <= n; j++) f[i][j] = min(f[i-1][j], f[i][j-1]) + a[i][j];
    printf("%d\n", f[n][n]);
    return 0;
}

一本通 1287：最低通行费

原文：https://www.cnblogs.com/Benjamin-cpp/p/10786669.html