10-16 LeetCode 120. Triangle
Description
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
给你一个三角形，找出从顶部到底部路径最小的路径值，每一步都只能找下一层与当前数相邻的两个数。
例子
如上述那个三角形，最短路径值为11. 2 + 3 + 5 + 1 = 11
Solution 1:
这个题目是一个很典型的动态规划的问题。动态规划适合解决的问题有如下特征：
可以转化为求解规模更小一些的的相同的子问题
子问题有最优解
多阶段规划
拿这个题目来说，想求到第一层的最短路径，可以先求出到第二层的每个点的最短路径，然后加上顶层的2就是最短路径。想求到第二层每个点的最短路径，可以先求出到第三层每个点的的最短路径，然后分别与第二层对应点相加求出第二层每个点的最短路径，这样依次类推下去。
代码
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
height = len(triangle)
result = triangle[-1]
for i in range(height-1, 0, -1):
temp = result[:]
result = []
for j in range(i):
result.append(min(triangle[i-1][j]+temp[j], triangle[i-1][j]+temp[j+1]))
return result[0]
感想
想做这个项目的时候没想到这学期课这么多，这几天学业压力比较重，有很多的实验，作业需要完成。我刷题都是在LeetCode上点击Pick problem随机选的，很幸运又找到个简单的题，让今天的任务可以很快完成。由于比较忙，自己做完这题就没去看别人的分析，不知道有没有什么更好的方法，可以自己去搜索。
