$$\color{Red}{最低通行费-详细题解}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

文字解析

本题看似是一个非常复杂的问题，因为如果出现了可以回头的情况，就无法用正常的动态规划去逐层分解，但是题目有一个关键信息，走过的方块数不能超过 2n - 1 个格子，这里我们仔细思考，在一个网格图中，衡量两点的距离的尺度

就不是坐标系尺度下的欧几里得距离，而是曼哈顿距离，对于（1，1）到（n，n）的曼哈顿距离，显然应该是n -1 + n - 1 = 2n - 2,而我们的起始点是在区域外，走到（1，1）这一步也是算在距离内。
因此本题隐含一个条件——》 每步必须往右或者下走，不然就不符合条件。

这样这个复杂的模型就被简化成了数字三角形模型，只不过和采花生不同，状态表示的属性没有变化，而状态表示的集合是维护最小值，因此我们需要对边界点i = 0以及j = 0的地方初始化无穷远，然后为了让f【1】【1】 = g【1】【1】，还需要把它前一步规划的点进行提前赋值。

1. java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 110, n;
    static int[][] a = new int[N][N];
    static int[][] f = new int[N][N];
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        n = sc.nextInt();
        for (int i = 0; i <= n; i++) Arrays.fill(f[i], 0x3f3f3f3f);
        f[0][1] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++){
                a[i][j] = sc.nextInt();
                f[i][j] = Math.min(f[i-1][j], f[i][j-1]) + a[i][j];
            }
        }
        System.out.println(f[n][n]);
    }
}

2. python代码

N = 110
g = [[0]*N for i in range(N)]
f = [[0x3f3f3f3f]*N for i in range(N)]

n = int(input())
for i in range(1, n+1):
    g[i][1:n+1] = map(int,input().split())

f[0][1] = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        f[i][j] = min(f[i-1][j], f[i][j-1]) + g[i][j]

print(f[n][n])