2
2021-02-19：给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角。沿途...
source link: https://studygolang.com/articles/33414
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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
}
}
执行结果如下：
图片
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK