题目内容

给定一个大小为 $m \times n$ 的二维整数网格 grid，其中每个单元格都填有一个非负整数。从左上角单元格出发，每次只能向下或向右移动一格，直到到达右下角单元格。一条路径的代价定义为沿途经过的所有单元格数字之和。请计算所有可行路径中代价的最小值。

约束条件

• 网格的行数 $m$ 和列数 $n$ 均不小于 $1$，且不超过 $200$。
• 每个单元格的数值 $\text{grid}[i][j]$ 不小于 $0$，且不超过 $200$。

输入描述

输入包含一个参数 grid，它是一个大小为 $m \times n$ 的二维整数列表，表示给定的网格。其中 grid[i][j] 表示第 $i$ 行第 $j$ 列的单元格数字。

输出描述

返回一个整数，表示从左上角到右下角的最小路径和。

样例1

输入

1 1
7

输出

7

说明

网格只有一个单元格，起点和终点都是该单元格。唯一路径不需要移动，路径代价就是单元格数字 7。

样例2

输入

1 4
2 0 3 1

输出

6

说明

网格只有一行，每次只能向右移动。唯一路径依次经过 2、0、3、1，路径和为 $2+0+3+1=6$。

样例3

输入

3 3
1 2 3
1 2 3
1 2 3

输出

8

说明

选择先向下两次、再向右两次的路径：1 → 1 → 1 → 2 → 3。

路径和为 $1+1+1+2+3=8$，所以最小路径和是 8。

样例4

输入

2 3
1 2 1
4 2 1

输出

5

说明

最优路径为向右、向右、向下：1 → 2 → 1 → 1。

路径和为 $1+2+1+1=5$，所以输出 5。