每天一道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)這個狀態方程的實現 上面思路已經說過
