每天一道leetcode64-最小路径和
- 2019 年 10 月 4 日
- 筆記
题目
每天一道leetcode64-最小路径和 分类：数组+动态规划（今天的题目涉及到了动态规划，直接在数组中选了一道题，难度还是有一些的，这里说一声抱歉） 中文链接： https://leetcode-cn.com/problems/minimum-path-sum/ 英文链接 https://leetcode.com/problems/minimum-path-sum/
题目详述
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
题目详解
思路
- 对于矩阵中的任意一个位置，都可以通过这个位置的上一个位置或者左边的这一个位置移动一步 来到达这个位置（因为每次只能向下或者向右移动一步。）；
- 对于矩阵中的任意一个位置（除去边界位置），dp(i,j) = min(dp(i-1,j),dp(i,j-1)) + grid(i,j)得到，dp(i-1,j)就是（i,j）左边的这一个点，dp(i,j-1)就是(i,j)的上一个点，比较这两个数的大小，取最小的加上grid（i,j）就是（i,j）这个位置的最小值
- 边界情况单独考虑，对于第一行和第一列，第一行只能是由左边的一个位置移动得来，第一列只能由它上面的位置移动得到（因为每次只能向下或者向右移动一步。）；
代码
class Solution { public int minPathSum(int[][] grid) { int rows = grid.length; int cols = 0; if(rows != 0) cols = grid[0].length; int [][] equation = new int[rows][cols]; for(int i=0;i<rows;i++) { for(int j=0;j<cols;j++) { if(i == 0 && j ==0) { equation[i][j] = grid[0][0]; }else if(i == 0) { equation[i][j] = equation[i][j-1] + grid[i][j]; }else if(j == 0) { equation[i][j] = equation[i-1][j] + grid[i][j]; }else{ if(equation[i][j-1] < equation[i-1][j]) equation[i][j] = equation[i][j-1] + grid[i][j]; else equation[i][j] = equation[i-1][j] + grid[i][j]; } } } return equation[rows-1][cols-1]; } }
代码讲解
- 3-7行 就是新建一个二维数组大小和grid一样，这个数组的每一个位置（i,j）用来记录到达grid(i,j)这里的路径和的最小值
- 8-10行 两次循环，用来遍历整个数组grid的；
- 12-14行 就是矩阵的左上角就是自己本身了~
- 15-17行 就是矩阵的第一行，就是用（i-1,j）位置的数加上grid(i,j)的值，得到（i,j）的位置的最小距离
- 18-20行 就是矩阵的第一列，只能由上一个位置到达（i,j）
- 21-25行 就是dp(i,j) = min(dp(i-1,j),dp(i,j-1)) + grid(i,j)这个状态方程的实现 上面思路已经说过
