LeetCode 120. Triangle

 关注

发布于: 2020 年 04 月 29 日

DescriptionGiven a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
﻿
For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
﻿
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
﻿
问题分析本题为典型的矩阵路径最优问题：从起点到终点的路径和最大、最小等；
本题中节点 A 的下一个遍历节点可能是：正下方的节点、或右下方的节点；
﻿
故，尝试使用动态规划进行求解：
令DP[i][j]表示从根节点到节点任意节点A[i][j]的最小路径和，则有：
DP[i][j] = min(DP[i-1][j-1], DP[i-1][j]) + A[i][j]
﻿
进一步地题目要求尽可能使用O(N)的空间复杂度，其中N为三角形的行数，也为最后一行的元素个数。
考虑到上述递推公式中，当前行的结果仅与上一行节点有关，因此可将二维DP简化为一维DP；
实现时，为了避免遍历过程中，对上一行结果（正上方、左上方节点）的值进行修改，此处选择从右至左的遍历顺序，完成DP过程。
Submission
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        rows = len(triangle)
        if(rows == 0):
            return 0
        if(rows == 1):
            return triangle[0][0]
        
        dp = [0 for i in range(rows)]
        i = 0
        while(i < rows):
            j = i
            while(j >= 0):
                if(i == 0):
                    dp[j] = triangle[i][j]
                elif(j == 0):
                    dp[j] = dp[j] + triangle[i][j]
                elif(j == i):
                    dp[j] = dp[j-1] + triangle[i][j]
                else:
                    dp[j] = min(dp[j-1], dp[j]) + triangle[i][j]
                j = j - 1
            i = i + 1
        
        res = dp[0]
        for x in dp:
            res = min(res, x)
        return res
        
﻿
如有描述不当之处，欢迎留言互动！