题目大意：给定一个triangle，找出从上到下的和的最小值，每一步只能找下一行的相连的数字
解题思路：经典动态规划题。假如找到了上一层的每个点的最小值，那么下一层的最小值可以通过上一层最小值得到。
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
[
[2],
[5,6],
[11,10,13],
[15,11,18,16]
]
状态：\(f[i][j]\)表示走到第\(i\)行第\(j\)列的最小值
那么我们有
转移：\(f[i][j] = \mbox{min}(f[i - 1][j], f[i - 1][j - 1]) + \mbox{triangle}\)
def minimumTotal(self, triangle):
n = len(triangle)
# f[i][j] = min(f[i - 1][j], f[i - 1][j - 1]) + triangle
# padding
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)
因为\(f[i]\)只跟\(f[i-1]\)有关系，所有可以使用滚动数组来压缩空间。注意要使用deepcopy。
def minimumTotal(self, triangle):
n = len(triangle)
# padding
# 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:])
第三种办法，直接修改triangle，这样不需要额外的空间。因为直接修改triangle，所以不需要padding，注意相应的i和j的起始值也要改变。
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])