# leetcode 120. Triangle

120. Triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

[
[2],
[5,6],
[11,10,13],
[15,11,18,16]
]


def minimumTotal(self, triangle):
n = len(triangle)
# f[i][j] = min(f[i - 1][j], f[i - 1][j - 1]) + triangle
f = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, i + 1):
f[i][j] = triangle[i - 1][j - 1]
if i == 1 and j == 1:
continue
if j == 1:
f[i][j] += f[i - 1][j]
elif j == i:
f[i][j] += f[i - 1][j - 1]
else:
f[i][j] += min(f[i - 1][j], f[i - 1][j - 1])
return min(f[n][1:])

if __name__ == __main__:
triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
Solution().minimumTotal(triangle)


def minimumTotal(self, triangle):
n = len(triangle)
# f[i][j] = min(f[i - 1][j], f[i - 1][j - 1]) + triangle
f = [[0 for _ in range(n + 1)] for _ in range(2)]
for i in range(1, n + 1):
for j in range(1, i + 1):
f[1][j] = triangle[i - 1][j - 1]
if i == 1 and j == 1:
continue
if j == 1:
f[1][j] += f[0][j]
elif j == i:
f[1][j] += f[0][j - 1]
else:
f[1][j] += min(f[0][j], f[0][j - 1])
f[0] = f[1][:]
return min(f[0][1:])


def minimumTotal(self, triangle):
n = len(triangle)
t = triangle
# t[i][j] = minTotalOf(i, j)
# t[i][j] += min(t[i - 1][j], t[i - 1][j - 1])
for i in range(0, n):
for j in range(0, i + 1):
if i == 0 and j == 0:
continue
if j == 0:
t[i][j] += t[i - 1][j]
elif j == i:
t[i][j] += t[i - 1][j - 1]
else:
t[i][j] += min(t[i - 1][j], t[i -1][j - 1])
return min(t[n - 1])