问题描述
给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。
下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
例子
image.png
解题思路
动态规划
一开始我是这样想的，从第一行中选取最小元素，然后再选取第二行与第一行选取的数字相邻的最小元素，依此类推。仔细一想，行不通，因为若下面的行有的元素很小呢？
之后又想了想，把每一行都从小到大排序，然后选取每行的第一个元素不就行了，但是不能保证相邻。
最终还是老老实实的遍历所有可能性，存储所有路径的最小和到一个新的dp二维列表。
pyhton实现
class Solution:
def minFallingPathSum(self, A: List[List[int]]) -> int:
dp=[[0 for _ in range(len(A))] for _ in range(len(A[0]))]#二维列表
for i in range(len(A)):
for j in range(len(A[0])):
if i==0: #第一行就直接赋值
dp[i][j]=A[i][j]
else:
if j==0: #左边界
dp[i][j]=min(dp[i-1][j],dp[i-1][j+1])+A[i][j]
elif j==len(A[0])-1: #右边界
dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+A[i][j]
else:
dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1])+A[i][j]
#print(dp)
return min(dp[len(A)-1]) #输出最后一行的最小元素。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-falling-path-sum
