2021-02-19: Given a two-dimensional array matrix, a person must start at the top left corner and end up at the bottom right corner. You can only go down or to the right, and all the numbers along the way add up to the sum of the distances. What is the minimum distance sum?

2021-02-19: Natural wisdom. In general, you will consider the right and the bottom of dp[I][j], and you will choose the smallest one, although you can be sure that the next step is the minimum, but the next step is not necessarily the minimum, not the optimal path. Reverse thinking, dp[I][j] left and top, who chooses who is smaller, left and top have been determined, certain path is the best. This is a space compression trick, so dp doesn’t need a 2-d array, dp needs a 1-D array. This reveals a truth of life: the future is uncertain, the past is certain. The code is written in Golang, and the code is as follows:

package main

import "fmt"

func main(a) {
    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
    }
}
Copy the code

The result is as follows:

Left God Java code reviews