[leetcode/lintcode 题解] 算法面试真题详解：下降路径最小和

描述
给定一个方形整数数组 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])

更多题解参考：九章官网solution

本文转自网络，原文链接：https://developer.aliyun.com/article/783838
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！