LintCode Q109 Triangle in Python

  • Jinhai ZHOU
  • 3 Minutes
  • 2016年12月21日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
"""
@param triangle: a list of lists of integers.
@return: An integer, minimum path sum.
"""
def minimumTotal(self, triangle):
# write your code here
# dynamic programming
# time complexity: O(row*col)
# space complexity: O(1) <- use input triangle as dp cache
for row in xrange(1, len(triangle)):
for col in xrange(len(triangle[row])):
if col - 1 >= 0 and col < len(triangle[row - 1]):
triangle[row][col] += min(triangle[row - 1][col], triangle[row - 1][col - 1])
elif col - 1 < 0 :
triangle[row][col] += triangle[row - 1][col]
else: # col >= len(triangle[row - 1])
triangle[row][col] += triangle[row - 1][col - 1]
return min(triangle[-1])
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。