[LintCode 109] 数字三角形(Python)

题目描述

给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。

注意事项
如果你只用额外空间复杂度O(n)的条件下完成可以获得加分，其中n是数字三角形的总行数。

样例
比如，给出下列数字三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。

思路

自底向上遍历。并用一个辅助列表来记录当前行各点到底部的最小路径和。

代码

class Solution:
    """
    @param: triangle: a list of lists of integers
    @return: An integer, minimum path sum
    """
    def minimumTotal(self, triangle):
        # write your code here
        res = 0
        if triangle is None or len(triangle) == 0:
            return res
        # 从后往前遍历
        # 辅助空间记录当前行各节点到底部的最小值
        tmp = triangle[-1]
        for i in range(len(triangle) - 1, -1, -1):
            if i + 1 < len(triangle):
                for j in range(len(triangle[i])):
                    tmp[j] = min(tmp[j], tmp[j + 1]) + triangle[i][j]
        return tmp[0]

复杂度分析

时间复杂度$O(n^2)$，空间复杂度$O(n)$。

最后

以上就是执着野狼为你收集整理的[LintCode 109] 数字三角形(Python)的全部内容，希望文章能够帮你解决[LintCode 109] 数字三角形(Python)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。