h310. 网格最低费用

题目描述

给定一个 $n$ 行 $m$ 列的非负整数网格。从左上角出发，每次只能向右或向下移动一格，直到右下角。

经过一个格子就要支付该格子的费用，起点和终点也计费。求一条路径的最小总费用。

输入格式

第一行输入两个整数 $n,m$。

接下来 $n$ 行，每行输入 $m$ 个整数，表示格子费用。

输出格式

输出一个整数，表示最小总费用。

数据范围

• $1\le n,m\le 500$
• $0\le a_{i,j}\le 1000$

样例

3 4
1 3 1 5
2 2 4 2
5 1 1 1

8

标签：动态规划、网格动态规划