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

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代码

评论

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