题解 | #矩阵的最小路径和# go + 动态规划

go + 动态规划

1. 先初始化dp数组 第一行、第一列 以及 dp[0][0] = matrix[0][0]
2. 转移方程为： dp[i][j] = min(dp[i-1][j] , dp[i][j-1]) + matrix[i][j]
3. 结果为 dp[rows-1][cols-1]

func minPathSum( matrix [][]int ) int {
    // write code here
    if len(matrix) == 0 {
        return 0
    }

    rows := len(matrix)
    cols := len(matrix[0])

    dp := make([][]int, rows)
    for i:=0; i< rows; i++{
        dp[i] = make([]int, cols)
    }

    dp[0][0] = matrix[0][0]

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

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


    for i:=1; i< rows; i++{
        for j:=1; j< cols; j++{
            if dp[i-1][j] > dp[i][j-1] {
                dp[i][j] = matrix[i][j] + dp[i][j-1]
            }else{
                dp[i][j] = matrix[i][j] + dp[i-1][j]
            }
        }
    }

    return dp[rows-1][cols-1]
}