最小路径和

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

约定

• 每次只能向下或者向右移动一步。
• 网格至少有一个格子。

输入

• grid：二维非负整数数组，行数 [1, 200]，列数 [1, 200]。

输出

最小路径和。

示例一

输入：

grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]

输出：

7

解释：路径 1 -> 3 -> 1 -> 1 -> 1，和为 7。

示例二

输入：

grid = [[1, 2, 3], [4, 5, 6]]

输出：

12

复杂度要求

• 时间 O(m·n)，空间 O(1)（原地 DP）。