leetcode 64. 最小路径和
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
题解:
1.一个包含非负整数的 m x n 网格
2.从左上角到右下角的路径,找出一条路径和最小
3.每次只能向下或者向右移动一步
4.题目本质上和174. 地下城游戏一样
示例:
输入:
[[1,3,1],
[1,5,1],
[4,2,1]]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
解题思路:
-
和174. 地下城游戏一样思路,考虑倒序
-
因为都为非负整数,可以从0开始累计路径和
-
累加每一步下方和右方最小的路径节点,从而能得到一个路径和最小
-
最后回到dp左上角的位置得到一个路径最小的和
C/C++题解:
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
dp[n][m - 1] = dp[n - 1][m] = 0;//都为非负整数,从0累计路径和
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {//从尾模拟往右、下走的过程
dp[i][j] = grid[i][j] + min(dp[i + 1][j], dp[i][j + 1]);}}
// 累加每一步下方和右方最小的路径节点,从而能得到一个路径和最小的
return dp[0][0];}};//回到左上角得到一条路径的最小和
Debug结果:
Java题解:
class Solution {
public int minPathSum(int[][] grid) {
int n = grid.length, m = grid[0].length;
int[][] dp = new int[n + 1][m + 1];
for(int i=0;i<dp.length;i++){
for(int j=0;j<dp[i].length;j++){
dp[i][j] = Integer.MAX_VALUE; } }
dp[n][m - 1] = dp[n - 1][m] = 0;//都为非负整数,从0累计路径和
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {//从尾模拟往右、下走的过程
dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);}}
// 累加每一步下方和右方最小的路径节点,从而能得到一个路径和最小的
return dp[0][0];}}//回到左上角得到一条路径的最小和
Debug结果:
Python题解:
class Solution(object):
def minPathSum(self, grid):
""":type grid: List[List[int]]:rtype: int"""
n, m = len(grid), len(grid[0])
dp = [[sys.maxint for _ in range(m+1)] for _ in range(n+1)]
dp[n][m - 1] = dp[n - 1][m] = 0 #都为非负整数,从0累计路径和
for i in range(n-1, -1, -1):
for j in range(m-1, -1, -1):
dp[i][j] = grid[i][j] + min(dp[i + 1][j], dp[i][j + 1])
#累加每一步下方和右方最小的路径节点,从而能得到一个路径和最小的
return dp[0][0] #回到左上角得到一条路径的最小和
Debug结果:
更多题解移步公众号免费获取