dp002

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from typing import List

Layer_nums = List[int]


def yh_triangle(nums: List[Layer_nums]) -> int:
"""
从根节点开始向下走,过程中经过的节点,只需存储经过它时最小的路径和
:param nums:
:return:
"""
assert len(nums) > 0
n = len(nums) # 层数
memo = [[0]*n for i in range(n)]
memo[0][0] = nums[0][0]

for i in range(1, n):
for j in range(i+1):
# 每一层首尾两个数字,只有一条路径可以到达
if j == 0:
memo[i][j] = memo[i-1][j] + nums[i][j]
elif j == i:
memo[i][j] = memo[i-1][j-1] + nums[i][j]
else:
memo[i][j] = min(memo[i-1][j-1] + nums[i][j], memo[i-1][j] + nums[i][j])
return min(memo[n-1])


def yh_triangle_space_optimization(nums: List[Layer_nums]) -> int:
assert len(nums) > 0
n = len(nums)
memo = [0] * n
memo[0] = nums[0][0]

for i in range(1, n):
for j in range(i, -1, -1):
if j == i:
memo[j] = memo[j-1] + nums[i][j]
elif j == 0:
memo[j] = memo[j] + nums[i][j]
else:
memo[j] = min(memo[j-1] + nums[i][j], memo[j] + nums[i][j])
return min(memo)


def yh_triangle_bottom_up(nums: List[Layer_nums]) -> int:
assert len(nums) > 0
n = len(nums)
memo = nums[-1].copy()

for i in range(n-1, 0, -1):
for j in range(i):
memo[j] = min(memo[j] + nums[i-1][j], memo[j+1] + nums[i-1][j])
return memo[0]


if __name__ == '__main__':
nums = [[3], [2, 6], [5, 4, 2], [6, 0, 3, 2]]
print(yh_triangle(nums))
print(yh_triangle_space_optimization(nums))
print(yh_triangle_bottom_up(nums))