最小路径和 中等🌟🌟🌟🌟🌟
问题描述
原文链接：64. 最小路径和
给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
代码实现
Java
class Solution {
/*动态规划三部曲
1、定义数组含义
dp[i][j]:当到达 (i,j) 这个位置时，最小路径和为 dp[i][j]。
2、关系式
dp[i][j]. dp[i-1][j] dp[i][j-1]
如何才能到达 （i，j）
（1）要么从 （i-1,j) 这个位置向下走一步=>dp[i][j] = dp[i-1][j] + grid[i][j]
（2）要么是从(i,j-1)这个位置向右走一步=>dp[i][j] = dp[i][j-1] + grid[i][j]
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
3、初始值
dp[0][0~m-1]
dp[0~n-1][0]
*/
public int minPathSum(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][] dp = new int[n][m];
// 求初始值
dp[0][0] = grid[0][0];
for(int j = 1; j < m; j++){
dp[0][j] = dp[0][j-1] + grid[0][j];
}
for(int i = 1; i < n; i++){
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[n-1][m-1];
}
}
Python
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
"""
动态规划三部曲
1、定义数组含义
dp[i][j]:当到达 (i,j) 这个位置时，最小路径和为 dp[i][j].
2、关系式
dp[i][j], dp[i-1][j], dp[i][j-1]
如何才能到达 (i, j):
(1) 要么从 (i-1, j) 这个位置向下走一步 => dp[i][j] = dp[i-1][j] + grid[i][j]
(2) 要么是从 (i, j-1) 这个位置向右走一步 => dp[i][j] = dp[i][j-1] + grid[i][j]
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
3、初始值
dp[0][0~m-1]
dp[0~n-1][0]
"""
n = len(grid)
m = len(grid[0])
dp = [[0 for _ in range(m)] for _ in range(n)]
# 求初始值
dp[0][0] = grid[0][0]
for j in range(1, m):
dp[0][j] = dp[0][j - 1] + grid[0][j]
for i in range(1, n):
dp[i][0] = dp[i - 1][0] + grid[i][0]
for i in range(1, n):
for j in range(1, m):
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
return dp[n - 1][m - 1]
C++
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
/*
动态规划三部曲
1、定义数组含义
dp[i][j]:当到达 (i,j) 这个位置时，最小路径和为 dp[i][j].
2、关系式
dp[i][j], dp[i-1][j], dp[i][j-1]
如何才能到达 (i, j):
(1) 要么从 (i-1, j) 这个位置向下走一步 => dp[i][j] = dp[i-1][j] + grid[i][j]
(2) 要么是从 (i, j-1) 这个位置向右走一步 => dp[i][j] = dp[i][j-1] + grid[i][j]
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
3、初始值
dp[0][0~m-1]
dp[0~n-1][0]
*/
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> dp(n, vector<int>(m, 0));
// 求初始值
dp[0][0] = grid[0][0];
for (int j = 1; j < m; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < n; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[n - 1][m - 1];
}
};
Go
func minPathSum(grid [][]int) int {
/*
动态规划三部曲
1、定义数组含义
dp[i][j]:当到达 (i,j) 这个位置时，最小路径和为 dp[i][j].
2、关系式
dp[i][j], dp[i-1][j], dp[i][j-1]
如何才能到达 (i, j):
(1) 要么从 (i-1, j) 这个位置向下走一步 => dp[i][j] = dp[i-1][j] + grid[i][j]
(2) 要么是从 (i, j-1) 这个位置向右走一步 => dp[i][j] = dp[i][j-1] + grid[i][j]
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
3、初始值
dp[0][0~m-1]
dp[0~n-1][0]
*/
n := len(grid)
m := len(grid[0])
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
}
// 求初始值
dp[0][0] = grid[0][0]
for j := 1; j < m; j++ {
dp[0][j] = dp[0][j-1] + grid[0][j]
}
for i := 1; i < n; i++ {
dp[i][0] = dp[i-1][0] + grid[i][0]
}
for i := 1; i < n; i++ {
for j := 1; j < m; j++ {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
}
}
return dp[n-1][m-1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
