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

题目大意

参考: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]

总结