本文主要是介绍2021-02-19:给定一个二维数组matrix,一个人必须从左上角出发,最后到达右下角。沿途只可以向下或者向右走,沿途的数字都累加就是距离累加和。请问最小距离累加和是多少?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
2021-02-19:给定一个二维数组matrix,一个人必须从左上角出发,最后到达右下角。沿途只可以向下或者向右走,沿途的数字都累加就是距离累加和。请问最小距离累加和是多少?
福哥答案2021-02-19:
自然智慧即可。
一般会考虑dp[i][j]的右边和下边,谁小选谁,虽然你能确定下一步是最小值,但是下一步的以后就不一定是最小值了,不是路径最优。逆向思维,dp[i][j]的左边和上边,谁小选谁,左边和上边已经确定了,肯定路径最优。这道题可以用空间压缩技巧,所以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代码
评论
这篇关于2021-02-19:给定一个二维数组matrix,一个人必须从左上角出发,最后到达右下角。沿途只可以向下或者向右走,沿途的数字都累加就是距离累加和。请问最小距离累加和是多少?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!