【DP】931. Minimum Falling Path Su

题目描述：

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

解题思路：

这道题是求最小下降路径和，即位置 (row, col) 可以到达位置 (row+1, col-1)、(row+1, col)、(row+1, col+1) 。

很明显这是一道动态规划的题目。用 dp[row][col] 表示到达位置 (row, col) 的最小累计和，它的计算等于当前位置 A[row][col] 加上 (row-1, col-1)、(row-1, col) 和 (row-1, col+1) 这三个位置的最小值，即：
dp[row][col] = A[row][col] + min(dp[row-1][col-1], dp[row-1][col], dp[row-1][col+1])
因此，我们只需要从上到下遍历方阵，更新每个位置的累加最小值。最后，dp 最后一行的最小值就是最终的答案。

注意：在编程的时候要初始化第一行 dp[0] = A[0]，同时在遍历每一行时要注意最左和最右位置的边界条件。

Python3 实现：

class Solution:
    def minFallingPathSum(self, A: List[List[int]]) -> int:
        lens = len(A)
        dp = [[0] * lens for _ in range(lens)]
        dp[0] = A[0]  # 初始化第一行
        for row in range(1, lens):
            dp[row][0] = A[row][0] + min(dp[row-1][0], dp[row-1][1])
            for col in range(1, lens-1):
                dp[row][col] = A[row][col] + min(dp[row-1][col-1], dp[row-1][col], dp[row-1][col+1])
            dp[row][lens-1] = A[row][lens-1] + min(dp[row-1][lens-2], dp[row-1][lens-1])
        return min(dp[-1])