2021-02-19：給定一個(gè)二維數(shù)組matrix，一個(gè)人必須從左上角出發(fā)
2021-02-19：給定一個(gè)二維數(shù)組matrix，一個(gè)人必須從左上角出發(fā)，最后到達(dá)右下角。沿途只可以向下或者向右走，沿途的數(shù)字都累加就是距離累加和。請(qǐng)問最小距離累加和是多少？
福哥答案2021-02-19：
自然智慧即可。
一般會(huì)考慮dp[i][j]的右邊和下邊，誰小選誰，雖然你能確定下一步是最小值，但是下一步的以后就不一定是最小值了，不是路徑最優(yōu)。逆向思維，dp[i][j]的左邊和上邊，誰小選誰，左邊和上邊已經(jīng)確定了，肯定路徑最優(yōu)。這道題可以用空間壓縮技巧，所以dp不需要二維數(shù)組，用一維數(shù)組即可。這揭示了一個(gè)人生道理：未來是不確定的，過去是確定的。
代碼用golang編寫，代碼如下：
```go
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
? ? }
}
```
執(zhí)行結(jié)果如下：
***
[左神java代碼](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class21/Code01_MinPathSum.java)
[評(píng)論](https://user.qzone.qq.com/3182319461/blog/1613690661)
