forked from yingl/LintCodeInPython
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtriangle.py
More file actions
25 lines (24 loc) · 860 Bytes
/
Copy pathtriangle.py
File metadata and controls
25 lines (24 loc) · 860 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# -*- coding: utf-8 -*-
class Solution:
"""
@param triangle: a list of lists of integers.
@return: An integer, minimum path sum.
"""
def minimumTotal(self, triangle):
# write your code here
i = 1
dists = [triangle[0][0]]
while i < len(triangle):
new_dists = [triangle[i][0] + dists[0]]
for j in xrange(1, len(triangle[i])):
'''
dists为上一层记录，
new_dists保存根据上一层记录计算出的当前层数据。
'''
if j == (len(triangle[i]) - 1):
new_dists.append(triangle[i][-1] + dists[-1])
else:
new_dists.append(triangle[i][j] + min(dists[j - 1], dists[j]))
dists = new_dists
i += 1
return min(dists)