题目
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例一：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。示例二：
代码语言：javascript复制输入：grid = [[1,2,3],[4,5,6]]
输出：12提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= gridi <= 200
解题
解法一
思路
由于题中指出“每次只能向下或者向右移动一步。”，因此本题还是相对比较简单的。
首先定义一个数组dp[][]长度大小和题给数组相同，dp[i][j]数组中存储的是到达每个索引处的最短路径。通过循环可以将dp[][]填满。由于每次只能向下或者向右移动一步，因此第一列和第一行的可以优先快速被填充完，然后接下来再继续填充中间的数组即可。
解决
代码语言：javascript复制class Solution {
public int minPathSum(int[][] grid) {
//首先初始化定义一个和题给数组大小一样的数组，dp用来记录最短路径
int[][] dp = new int[grid.length][grid[0].length];
//第一个位置的路径是固定
dp[0][0] = grid[0][0];
//将第一列进行填充
for(int i=1;i结果
代码语言：javascript复制> 2023/07/14 14:36:58
解答成功:
执行耗时:2 ms,击败了92.29% 的Java用户
内存消耗:42.7 MB,击败了88.21% 的Java用户
