第十五次作业

leetcode题目：

解题思路：

动态规划：不妨令minimum为位置（i，j）的最小路径，minimum可以就是triangle。

从第二行开始有：

if j==0: triangle[i][0]+=triangle[i-1][0] elif j==i: triangle[i][i] += triangle[i - 1][i-1] else: triangle[i][j]+=min(triangle[i-1][j],triangle[i-1][j-1])

最后返回：

min(triangle[m-1])

代码：

class Solution: def minimumTotal(self, triangle): """ :type triangle: List[List[int]] :rtype: int """ m=len(triangle) if m==1: return triangle[0][0] for i in range(1,m): for j in range(0,i+1): if j==0: triangle[i][0]+=triangle[i-1][0] elif j==i: triangle[i][j] += triangle[i - 1][j-1] else: triangle[i][j]+=min(triangle[i-1][j],triangle[i-1][j-1]) return min(triangle[m-1])

结果：

其实还有更优的解法，就是反过来进行算法，从最后一行开始进行动态规划，最后triangle[0][0]就是要求的最小路径。