题解 | #矩阵的最小路径和#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param matrix int整型二维数组 the matrix
 * @return int整型
 */
func minPathSum(matrix [][]int) int {

	// 最小路径和 matrix[i][j] = min(dp[i-1][j],dp[i,j-1]) + a[i][j]
	// 初始化 dp[0][0] = a[0][0]
	// 边界情况处理：第一行和第一列需要特殊处理，因为第一行的位置只能从左边来，第一列的位置只能从上面来。
	n, m := len(matrix), len(matrix[0])
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, m)
	}

	dp[0][0] = matrix[0][0]
	for i := 1; i < n; i++ {
		dp[i][0] = dp[i-1][0] + matrix[i][0]
	}
	for j := 1; j < m; j++ {
		dp[0][j] = dp[0][j-1] + matrix[0][j]
	}

	for i := 1; i < n; i++ {
		for j := 1; j < m; j++ {
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
		}
	}

	return dp[n-1][m-1]
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}