蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】Triangle 三角形最小路径和

发表于 更新于 分类于 阅读次数： Valine：

题目大意

参考：https://shenjie1993.gitbooks.io/leetcode-python/120%20Triangle.html
将一个二维数组排列成金字塔的形状，找到一条从塔顶到塔底的路径，使路径上的所有点的和最小，从上一层到下一层只能挑相邻的两个点中的一个。
注意点：

最好将空间复杂度控制在**O(n)**，n是金字塔的高度

解题思路

二维DP

金字塔为：

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

反过来直接往上加：

1
dp[i][j] = min(dp[i-1][j],dp[i-1][j+1])+tri[i][j]  #大致意思，理解就行
1
2
3
4
4 1  8  3
7 6  10
9 10
11

一维DP

典型的动态规划问题，先将问题转化一下，把每一行的数列都左对齐，如下：

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

可以看出来，其实上一行到下一行就两个选择，横坐标不变或加一。
dp[i]表示从底层到这一层的第i个元素所有路径中最小的和。
递推关系就是 dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
即下一行与它相邻的两个节点中和比较小的再加上它自己的值。这样在一维空间完成了dp，符合题目挑战。

dp数组变化：

[4,1,8,3]
[7,6,10,3]
…

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        n = len(triangle)
        dp = triangle[-1]
        for i in range(n - 2, -1, -1):
            for j in range(i + 1):  # 从倒数第二层开始网上，变化数字，dp[-1]一开始就用不到了
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
        print dp
        return dp[0]

总结