對(duì)動(dòng)態(tài)規(guī)劃仍然不熟，而且最近想掌握一下Go語言，所以用它來做一下算法題

題目

Given a square array of integers A, we want the minimum sum of a falling path through A.

A falling path starts at any element in the first row, and chooses one element from each row. The next row's choice must be in a column that is different from the previous row's column by at most one.

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation: 
The possible falling paths are:
[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
The falling path with the smallest sum is [1,4,7], so the answer is 12.

Note:

• 1 <= A.length == A[0].length <= 100
• -100 <= A[i][j] <= 100

題解

這道題是很簡(jiǎn)單的動(dòng)態(tài)規(guī)劃題，題目解析在注釋里已經(jīng)有了。

func minFallingPathSum(A [][]int) int{
    //題目：二維數(shù)組，像水流一樣降落（降落時(shí)不能隔開超過一列），求降落總和最大
    //狀態(tài)：當(dāng)以 A[row][col] 結(jié)尾時(shí)的最大總和
    rowNum := len(A)
    colNum := len(A[0])
    //構(gòu)建二維數(shù)組
    min := make([][]int, rowNum)
    for i:=0; i<rowNum; i++{
        min[i] = make([]int, colNum)
    }


    //計(jì)算min值
    min[0] = A[0]
    for row:=1; row<rowNum; row++{
        for col:= 0; col<colNum; col++{
            if col == 0{
                switch{
                case min[row-1][col] < min[row-1][col+1]:
                    min[row][col] = A[row][col] + min[row-1][col]
                default:
                    min[row][col] = A[row][col] + min[row-1][col+1]
                }
            } else if col == colNum-1{
                switch{
                case min[row-1][col] < min[row-1][col-1]:
                    min[row][col] = A[row][col] + min[row-1][col]
                default:
                    min[row][col] = A[row][col] + min[row-1][col-1]
                }
            } else{
                switch{
                case min[row-1][col-1] < min[row-1][col] && min[row-1][col-1] < min[row-1][col+1]:
                    min[row][col] = A[row][col] + min[row-1][col-1]
                case min[row-1][col] < min[row-1][col+1]:
                    min[row][col] = A[row][col] + min[row-1][col]
                default:
                    min[row][col] = A[row][col] + min[row-1][col+1]
                }
            }
        }
    }
    result := min[rowNum-1][0]
    for i:=1; i<colNum; i++{
        if min[rowNum-1][i] < result{
            result = min[rowNum-1][i]
        }
    }
    return result
}