Leetcode 120.三角形最小路径和

1 题目描述（Leetcode题目链接）

  给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。例如：

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

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
  说明：如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

2 题解

  本题为动态规划问题，可以构造一个矩阵或直接使用题目输入的数据来构造，定义$DP[i][j]$DP[i][j]为走到第$(i,j)$(i,j)个节点的最小路径，则状态转移为：
$DP[i][j] = min(DP[i-1][j-1] + triangle[i][j], DP[i-1][j] + triangle[i][j])$DP[i][j]=min(DP[i−1][j−1]+triangle[i][j],DP[i−1][j]+triangle[i][j])
如果直接使用输入的数据，那么就将上式中的$DP$DP均换为$triangle$triangle即可。

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        length = len(triangle)
        for i in range(1,length):
            for j in range(0,i+1):
                if j == 0:
                    triangle[i][j] = triangle[i-1][j] + triangle[i][j]
                    continue
                if j == i:
                    triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]
                    continue
                triangle[i][j] = min(triangle[i-1][j-1] + triangle[i][j], triangle[i-1][j] + triangle[i][j])
        return min(triangle[length-1])

  如果考虑只用$O(n)$O(n)的额外空间，即只开辟一个一维数组，则可以使用自底向上的方法，先将$DP$DP数组初始化为$triangle$triangle的最后一行，然后依据下面的状态转移方程，最后得到的结果是$DP[0]$DP[0]。
$DP[j] = min(DP[j] + triangle[i][j], DP[j+1]+triangle[i][j])$DP[j]=min(DP[j]+triangle[i][j],DP[j+1]+triangle[i][j])

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        length = len(triangle)
        DP = triangle[-1]
        i = length - 2
        while i >= 0:
            for j in range(0, 1+i):
                DP[j] = min(DP[j] + triangle[i][j], DP[j+1]+triangle[i][j])
            i -= 1
        return DP[0]

• 点赞
• 收藏
• 分享
• • 文章举报

就叫昵称吧 发布了32 篇原创文章 · 获赞 53 · 访问量 2万+ 私信 关注