-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path120.triangle.py
More file actions
114 lines (96 loc) · 3.35 KB
/
120.triangle.py
File metadata and controls
114 lines (96 loc) · 3.35 KB
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
# Tag: Array, Dynamic Programming
# Time: O(N^2)
# Space: O(N)
# Ref: -
# Note: -
# Video: https://youtu.be/cQKJpyKC3JI
# Given a triangle array, return the minimum path sum from top to bottom.
# For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
#
# Example 1:
#
# Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
# Output: 11
# Explanation: The triangle looks like:
# 2
# 3 4
# 6 5 7
# 4 1 8 3
# The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
#
# Example 2:
#
# Input: triangle = [[-10]]
# Output: -10
#
#
# Constraints:
#
# 1 <= triangle.length <= 200
# triangle[0].length == 1
# triangle[i].length == triangle[i - 1].length + 1
# -104 <= triangle[i][j] <= 104
#
#
# Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
for i in range(n - 1, 0, -1):
for j in range(i):
triangle[i - 1][j] += min(triangle[i][j], triangle[i][j + 1])
return triangle[0][0]
# DP top-down O(N^2)
class Solution(object):
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
m = len(triangle[-1])
dp = [0 for i in range(m)]
dp[0] = triangle[0][0]
for i in range(1, n):
for j in range(len(triangle[i]) - 1, -1, -1):
if j == 0:
dp[j] = dp[j] + triangle[i][j]
elif j == len(triangle[i]) - 1:
dp[j] = dp[j - 1] + triangle[i][j]
else:
dp[j] = min(dp[j - 1], dp[j]) + triangle[i][j]
return min(dp)
# divideAndConquer + memory O(N^2) since (x, y), x, y each has N possible numbers
class Solution(object):
def minimumTotal(self, triangle: List[List[int]]) -> int:
memory = {}
return self.helper(triangle, 0, 0, memory)
def helper(self, triangle, i, j, memory):
if i == len(triangle):
return 0
if (i, j) not in memory:
left = self.helper(triangle, i + 1, j, memory)
right = self.helper(triangle, i + 1, j + 1, memory)
memory[(i, j)] = triangle[i][j] + min(left, right)
return memory[(i, j)]
# DFS O(2^N)
class Solution(object):
def minimumTotal(self, triangle: List[List[int]]) -> int:
return self.helper(triangle, 0, 0)
def helper(self, triangle, i, j):
if i == len(triangle):
return 0
left = self.helper(triangle, i + 1, j)
right = self.helper(triangle, i + 1, j + 1)
return triangle[i][j] + min(left, right)
# DFS O(2^N)
class Solution(object):
def minimumTotal(self, triangle: List[List[int]]) -> int:
self.min_sum = float('inf')
tmp = []
self.helper(triangle, tmp, 0, 0)
return self.min_sum
def helper(self, triangle, tmp, i, j):
if i == len(triangle):
self.min_sum = min(self.min_sum, sum(tmp))
return
tmp.append(triangle[i][j])
self.helper(triangle, tmp, i + 1, j)
self.helper(triangle, tmp, i + 1, j + 1)
tmp.pop()