2021-02-19:给定一个二维数组matrix,一个人必须从左上角出发,最后到达右下角。沿途只可以向下或者向右走,沿途的数字都累加就是距离累加和。请问最小距离累加和是多少?

福大大架构师每日一题 · · 245 次点击 · · 开始浏览    

2021-02-19:给定一个二维数组matrix,一个人必须从左上角出发,最后到达右下角。沿途只可以向下或者向右走,沿途的数字都累加就是距离累加和。请问最小距离累加和是多少?

福哥答案2021-02-19:
自然智慧即可。
一般会考虑dp[i][j]的右边和下边,谁小选谁,虽然你能确定下一步是最小值,但是下一步的以后就不一定是最小值了,不是路径最优。逆向思维,dp[i][j]的左边和上边,谁小选谁,左边和上边已经确定了,肯定路径最优。这道题可以用空间压缩技巧,所以dp不需要二维数组,用一维数组即可。这揭示了一个人生道理:未来是不确定的,过去是确定的。
代码用golang编写,代码如下:

package main

import "fmt"

func main() {
    if true {
        arr := [][]int{
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12},
            {13, 14, 15, 16}}
        ret := minPathSum(arr)
        fmt.Println(ret)
    }
}
func minPathSum(m [][]int) int {
    row := len(m)
    if row == 0 {
        return 0
    }
    col := len(m[0])
    if col == 0 {
        return 0
    }
    dp := make([]int, col)
    dp[0] = m[0][0]
    for j := 1; j < col; j++ {
        dp[j] = dp[j-1] + m[0][j]
    }
    for i := 1; i < row; i++ {
        dp[0] += m[i][0]
        for j := 1; j < col; j++ {
            dp[j] = getMin(dp[j-1], dp[j]) + m[i][j]
        }
    }
    return dp[col-1]
}
func getMin(a int, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

执行结果如下:


图片

左神java代码
评论


有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

245 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传