0120. 三角形最小路径和

0120. 三角形最小路径和 #

  • 标签:数组、动态规划
  • 难度:中等

题目大意 #

描述:给定一个代表三角形的二维数组 triangletriangle 共有 n 行,其中第 i 行(从 0 开始编号)包含了 i + 1 个数。

我们每一步只能从当前位置移动到下一行中相邻的节点上。也就是说,如果正位于第 i 行第 j 列的节点,那么下一步可以移动到第 i + 1 行第 j 列的位置上,或者第 i + 1 行,第 j + 1 列的位置上。

要求:找出自顶向下的最小路径和。

说明

  • $1 \le triangle.length \le 200$。
  • $triangle[0].length == 1$。
  • $triangle[i].length == triangle[i - 1].length + 1$。
  • $-10^4 \le triangle[i][j] \le 10^4$。

示例

1
2
3
4
5
6
7
8
输入triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出11
解释如下面简图所示
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 112 + 3 + 5 + 1 = 11)。

解题思路 #

思路 1:动态规划 #

1. 划分阶段 #

按照行数进行阶段划分。

2. 定义状态 #

定义状态 dp[i][j] 表示为:从顶部走到第 i 行(从 0 开始编号)、第 j 列的位置时的最小路径和。

3. 状态转移方程 #

由于每一步只能从当前位置移动到下一行中相邻的节点上,想要移动到第 i 行、第 j 列的位置,那么上一步只能在第 i - 1 行、第 j - 1 列的位置上,或者在第 i - 1 行、第 j 列的位置上。则状态转移方程为:

dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]。其中 triangle[i][j] 表示第 i 行、第 j 列位置上的元素值。

4. 初始条件 #

在第 0 行、第 j 列时,最小路径和为 triangle[0][0],即 dp[0][0] = triangle[0][0]

5. 最终结果 #

根据我们之前定义的状态,dp[i][j] 表示为:从顶部走到第 i 行(从 0 开始编号)、第 j 列的位置时的最小路径和。为了计算出最小路径和,则需要再遍历一遍 dp[size - 1] 行的每一列,求出最小值即为最终结果。

思路 1:动态规划代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        size = len(triangle)
        dp = [[0 for _ in range(size)] for _ in range(size)]
        dp[0][0] = triangle[0][0]

        for i in range(1, size):
            dp[i][0] = dp[i - 1][0] + triangle[i][0]
            for j in range(1, i):
                dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]

        return min(dp[size - 1])

思路 1:复杂度分析 #

  • 时间复杂度:$O(n^2)$。两重循环遍历的时间复杂度是 $O(n^2)$,最后求最小值的时间复杂度是 $O(n)$,所以总体时间复杂度为 $O(n^2)$。
  • 空间复杂度:$O(n^2)$。用到了二维数组保存状态,所以总体空间复杂度为 $O(n^2)$。
本站总访问量  次  |  您是本站第  位访问者