三角形最小路径和
https://leetcode.cn/problems/triangle/description/?envType=study-plan-v2&envId=top-interview-150
激动的心，这是一道没看题解自己做出来的动态规划
动态规划：
- 原问题的解由子问题的解组成，换言之就是在处理大问题之前子问题一定已经处理过了。
- 如果在计算过程中，发现了很多重复计算，并且更大的问题里面会重复计算很多次小问题，这个时候也可以考虑采用动态规划的思路
2
3 4
6 5 7
4 1 8 3
动态规划最重要的就是要挖掘这个问题里面大问题和子问题的关系，按照一层一层来看：
- 如果问题只有第一层，那么答案就是第一层的第一个数2
- 如果问题有第二层，那么就是两种情况，2->3或者2->4
- 如果问题有第三层，那么是四种情况：2->3->6,2->3->5,2->4->5,2->4->7
- 如果问题有第四层，那么是八种情况。
以此类推，可以想到暴力解法应该是一个O(2^n)的样子，因为每个点都有两种可能。但是指数级别的算法是很不好的，因此要考虑是否能够优化时间复杂度，再回头看，发现在计算每一层的时候有很多重复计算的地方，因此可以把计算过的路径保留下来，以空间换时间的方式进行优化。
怎么动态规划呢？仔细推理可以发现，从顶点到每一个点的最优路径应该是唯一的，因此从顶点到每一个点的最小路径和也是唯一的，并且下一层的结果只和（相邻的）上一层的这个唯一的最优路径有关。因此可以用dp数组把这个唯一的数记录下来，这个dp数组的含义就是从顶点到当前点的唯一路径的最小路径之和。
解答如下
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
max_line = triangle[-1]
dp = [[None] * len(max_line) for _ in range(len(max_line))]
dp[0][0] = triangle[0][0]
for line_index, line in enumerate(triangle):
if line_index == 0:
continue
for col_index, col in enumerate(line):
if col_index - 1 < 0:
dp[line_index][col_index] = col + dp[line_index - 1][col_index]
if line_index - 1 >= 0 and col_index - 1 >=0:
if col_index > line_index - 1:
dp[line_index][col_index] = col + dp[line_index - 1][col_index - 1]
else:
dp[line_index][col_index] = col + min(dp[line_index - 1][col_index], dp[line_index - 1][col_index - 1])
return min(dp[-1])
print(Solution().minimumTotal(triangle=[[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]))
时间复杂度O(n^2)，因为有两重循环。空间复杂度O(n^2)，因为有二维dp数组。