image.png
解题思路：
-
dp[i][j]表示走到(i-1, j-1)点时的路径和，其状态由上一行的j-1、j、j+1列转移而来，取三个状态的最小值； - 考虑边界情况，即当
j=0时，只能由上一行最左侧的两个状态dp[i-1][j]、dp[i-1][j+1]转移而来，当j=len(A[0])-1时，只能由上一行最右侧的两个状态dp[i-1][j]、dp[i-1][j-1]转移而来; - 第一行的dp值即为A的第一行值；
dp[0]=A[0]
Python3代码：
class Solution:
def minFallingPathSum(self, A: List[List[int]]) -> int:
dp = [[0 for _ in A[0]] for _ in A]
dp[0] = A[0]
for i in range(1, len(A)):
for j in range(len(A[0])):
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-1], dp[i-1][j]) + A[i][j]
else:
dp[i][j] = min(min(dp[i-1][j], dp[i-1][j-1]), dp[i-1][j+1]) + A[i][j]
return min(dp[-1])
