动态规划之矩形最短路径和

题目

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小,每次只能向下或者向右移动一步.

思路

到达第 i 行第 j 列的最短路径和等于:
第 i-1 行第 j 列的最短路径和加第 i 行第 j 列
第 i 行第 j-1 列的最短路径和加第 i 行第 j 列

两者的最小值

最终源码

func calc(grid [][]int) int {
    length := len(grid)
    if length < 1 {
        return 0
    }
    dp := make([][]int, length)
    for i, each := range grid {
        dp[i] = make([]int, len(each))
    }
    dp[0][0] = grid[0][0]
    for i := 0; i < length; i++ {
        for j := 0; j < len(grid[i]); j++ {
            if i == 0 && j != 0 {
                dp[i][j] = dp[i][j-1] + grid[i][j]
            } else if j == 0 && i != 0 {
                dp[i][j] = dp[i-1][j] + grid[i][j]
            } else if i != 0 && j != 0 {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
            }
        }
    }
    return dp[length-1][len(dp[length-1])-1]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}