lc064

64.最小路径和

1. 题目描述

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

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

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

标签 数组 动态规划 矩阵

2. 解题

采用动态规划，由于路径的方向只能是向下或向右，所以网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。
其余的元素可以有从左边或上面两种路径到达，取其左边或者上面元素和的最小值，再加上此元素的值，即为该元素的最小路径和。