本文主要是介绍[LeetCode] 64. Minimum Path Sum,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题:https://leetcode.com/problems/minimum-path-sum/description/
题目
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example:
Input:
[[1,3,1],[1,5,1],[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
思路
题目大意
求从矩阵的左上角到右下角的最小路径和,每次只能向右和向下移动。
解题思路
方法一
动态规划 自顶向下 ,并带记录。
状态dp[i][j]: 从 dp[0][0] 到 dp[i][j] 的最短路径长度。
状态初始化:dp[i][j] = Integer.MAX_VALUE,dp[0][0] = grid[0][0]
状态转移方程:dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
class Solution {int [][]dp;public int getMinPath(int [][] grid,int r,int c){if(r<0 || c <0) return Integer.MAX_VALUE;if(dp[r][c]!=Integer.MAX_VALUE) return dp[r][c];dp[r][c] = Math.min(getMinPath(grid,r-1,c),getMinPath(grid,r,c-1)) + grid[r][c];return dp[r][c];}public int minPathSum(int[][] grid) {dp = new int[grid.length][grid[0].length];for(int i = 0;i<dp.length;i++)for(int j = 0 ;j<dp[0].length;j++)dp[i][j] = Integer.MAX_VALUE;dp[0][0] = grid[0][0];return getMinPath(grid,grid.length-1,grid[0].length-1);}
}
方法二
动态规划 自底向上
状态dp[i][j]: 从 dp[0][0] 到 dp[i][j] 的最短路径长度。
状态初始化:dp[0][0] = grid[0][0]
状态转移方程:dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
class Solution {public int minPathSum(int[][] grid) {int [][]dp = new int[grid.length][grid[0].length];dp[0][0] = grid[0][0];for(int i = 1;i<dp.length;i++) dp[i][0] = dp[i-1][0] + grid[i][0];for(int j = 1;j<dp[0].length;j++) dp[0][j] = dp[0][j-1] + grid[0][j];for(int i = 1;i<dp.length;i++)for(int j = 1 ;j<dp[0].length;j++)dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];return dp[grid.length-1][grid[0].length-1];}
}
方法三
动态规划 自底向上
- 状态dp[j]: 从 dp[0][0] 到 行遍历所在 dp[j] 的最短路径长度。
- 状态初始化 dp[j] = dp[j - 1] + grid[i][j],i ==0
- 状态转移方程:
dp[j] = dp[j] + grid[i][j], j==0;
dp[j] = Math.min(dp[j - 1], dp[j])+ grid[i][j],j !=0 ;
等式 右边的 dp[j] 相当于上一行的dp[j],dp[j-1]是这一行的。
class Solution {public int minPathSum(int[][] grid) {int[] dp = new int[grid[0].length];dp[0] = grid[0][0];for(int j = 1;j<dp.length;j++) dp[j] = dp[j-1]+ grid[0][j];for(int i = 1;i<grid.length;i++)for(int j =0;j<grid[0].length;j++){if(j==0) dp[j] = dp[j] + grid[i][j];else dp[j] = Math.min(dp[j - 1], dp[j])+ grid[i][j];}return dp[dp.length-1];}
}
这篇关于[LeetCode] 64. Minimum Path Sum的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!