4157 - 动态规划:数字矩阵最短路径

通过次数

111

提交次数

159

时间限制 : 1 秒
内存限制 : 128 MB

给定一个矩阵m,从左上角开始每次只能向右走或者向下走,最后达到右下角的位置,路径中所有  
数字累加起来就是路径和,返回所有路径的最小路径和,如果给定的m如下,那么路径  
1,3,1,0,6,1,0就是最小路径和,返回12. 
 

输入

一行表示数字矩阵的行和列,

第二行开始就是数字矩阵的数据了

 

输出

输出表示从所经过路径的最小值

样例

输入

4 4
1 3 5 9
8 1 3 4 
5 0 6 1
8 8 4 0

输出

12