CodeACM
HOT 100 · 多维动态规划 · LC 64

最小路径和:ACM 模式刷题

按标准输入读取测试数据,输出结果后可在 CodeACM 在线运行和提交。

题目描述

给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

输入格式

第一行输入 m 和 n,接下来 m 行输入网格。

输出格式

输出最小路径和。

数据范围

  • 1 ≤ m,n ≤ 200
  • 0 ≤ grid[i][j] ≤ 200

公开样例

样例 1

输入

3 3
1 3 1
1 5 1
4 2 1

输出

7

路径 1→3→1→1→1 的总和最小,为 7。

样例 2

输入

2 3
1 2 3
4 5 6

输出

12

最优路径为 1→2→3→6。

练习建议

先根据输入输出格式写出可运行程序,再用公开样例检查结果;遇到边界情况时,补充自测用例后提交。