描述
给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。
下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
- 1 <= A.length == A[0].length <= 100
- -100 <= Ai <= 100
在线评测地址：领扣题库官网
样例1
输入：[[1,2,3],[4,5,6],[7,8,9]]
输出：12
解释：
可能的下降路径有：
[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]
和最小的下降路径是 [1,4,7]，所以答案是 12。解题思路
到达元素Ai的最小路径是Ai - 1，Ai - 1和Ai - 1中的最小值，从第二行开始，我们给每个元素加上到达这个元素的路径最小值，那么最终的结果即为最后一行的最小值。
源代码
class Solution:
"""
@param A: the given array
@return: the minimum sum of a falling path
"""
def minFallingPathSum(self, A):
# Write your code here
# 给从第二行开始的每个元素都加上到这个元素的路径最小值
for i in range(1, len(A)):
for j in range(len(A[0])):
topleft = A[i-1][max(j-1, 0)]
topright = A[i-1][min(j+1, len(A) - 1)]
A[i][j] += min(topleft, topright, A[i-1][j])
return min(A[-1])
