对动态规划仍然不熟，而且最近想掌握一下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

题解

这道题是很简单的动态规划题，题目解析在注释里已经有了。

func minFallingPathSum(A [][]int) int{
    //题目：二维数组，像水流一样降落（降落时不能隔开超过一列），求降落总和最大
    //状态：当以 A[row][col] 结尾时的最大总和
    rowNum := len(A)
    colNum := len(A[0])
    //构建二维数组
    min := make([][]int, rowNum)
    for i:=0; i<rowNum; i++{
        min[i] = make([]int, colNum)
    }


    //计算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
}