关于福大大架构师每日一题:20210219给定一个二维数组matrix一个人必须从左上角出发最后到达右下角

2021-02-19：给定一个二维数组matrix，一个人必须从左上角登程，最初达到右下角。沿途只能够向下或者向右走，沿途的数字都累加就是间隔累加和。请问最小间隔累加和是多少？

福哥答案2021-02-19：
天然智慧即可。
个别会思考dpi的左边和下边，谁小选谁，尽管你能确定下一步是最小值，然而下一步的当前就不肯定是最小值了，不是门路最优。逆向思维，dpi的右边和上边，谁小选谁，右边和上边曾经确定了，必定门路最优。这道题能够用空间压缩技巧，所以dp不须要二维数组，用一维数组即可。这揭示了一个人生情理：将来是不确定的，过来是确定的。
代码用golang编写，代码如下：

package mainimport "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代码
评论