秒懂【最小路径和】！动态规划一步步拆解。

1.思路

从左上角到右下角，移动的方向是向左或者向下。在移动的过程中需要获取元素的值，因此需要将当前元素的值累计上。对于当前的状态，从上侧、左侧选择最小的。 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j]

alt

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self, matrix: List[List[int]]) -> int:
        # write code here
        m = len(matrix)
        n = len(matrix[0])
        # 1.定义状态.	i：矩阵的行; j：矩阵的列;dp[i][j]:从(0,0)到达矩阵坐标为(i,j)时的最小的路径和
        dp = [[0] * n for _ in range(m)]
        # 2. 初始化边界条件.dp[i][0] = a[i][0] + dp[i - 1][0]； dp[j][0] = a[j][0] + a[j - 1][0]；
        # 2.1 初始化左上角元素
        dp[0][0] = matrix[0][0]
        # 2.2 初始化第1列
        for i in range(1, m):
            # 只能来自于上侧
            dp[i][0] = dp[i - 1][0] + matrix[i][0]
        # 2.3 初始化第1行
        for j in range(1, n):
            # 只能来自于左侧
            dp[0][j] = dp[0][j - 1] + matrix[0][j]
        # 3.确定递推公式： dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j]
        for i in range(1, m):
            for j in range(1, n):
                # 上侧、左侧选择最小的
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j]
        # 4.  输出结果
        return dp[m - 1][n - 1]

2.2 Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        int m = matrix.length;
        int n = matrix[0].length;
        // 1.定义状态.  i：矩阵的行; j：矩阵的列;dp[i][j]:从(0,0)到达矩阵坐标为(i,j)时的最小的路径和
        int[][] dp = new int[m][n];
        // 2.初始化边界条件. dp[i][0]=a[i][0]+dp[i-1][0]； dp[j][0]=a[j][0]+a[j-1][0]；
        // 2.1 初始化左上角元素
        dp[0][0] = matrix[0][0];
        // 2.2 初始化第1列
        for (int i = 1; i < m; i++) {
            // 只能来自于上侧
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }
        //2.3 初始化第1行
        for (int j = 1; j < n; j++) {
            //只能来自于左侧
            dp[0][j] = dp[0][j - 1] + matrix[0][j];
        }
        // 3.确定递推公式： dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j]
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 上侧、左侧选择最小的
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
            }
        }
        // 4.输出结果
        return dp[m - 1][n - 1];
    }
}

2.3 Go代码

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param matrix int整型二维数组 the matrix
 * @return int整型
 */
func minPathSum(matrix [][]int) int {
	// write code here
	m := len(matrix)
	n := len(matrix[0])
	// 1.定义状态.	i：矩阵的行; j：矩阵的列;dp[i][j]:从(0,0)到达矩阵坐标为(i,j)时的最小的路径和
	dp := newArray(m, n)
	// 2.初始化边界条件.	dp[i][0]=a[i][0]+dp[i-1][0]； dp[j][0]=a[j][0]+a[j-1][0]；
	// 2.1 初始化左上角元素
	dp[0][0] = matrix[0][0]
	// 2.2 初始化第1列
	for i := 1; i < m; i++ {
		// 只能来自于上侧
		dp[i][0] = dp[i-1][0] + matrix[i][0]
	}
	// 2.3 初始化第1行
	for j := 1; j < n; j++ {
		//只能来自于左侧
		dp[0][j] = dp[0][j-1] + matrix[0][j]
	}
	// 3.确定递推公式： dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j]
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			// 上侧、左侧选择最小的
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
		}
	}
	// 4.输出结果
	return dp[m-1][n-1]
}

// 创建一个 m行n列的矩阵（二维数组）
func newArray(m int, n int) [][]int {
	arr := make([][]int, m)
	for i := 0; i < m; i++ {
		arr[i] = make([]int, n)
	}
	return arr
}
func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构