如何查找网站所有页面/网络营销软件站

题目来源：

　　https://leetcode.com/problems/triangle/

---

 

题意分析：

　　给定一个三角数组。找到自顶向下的最短路径。如：

[[2],[3,4],[6,5,7],[4,1,8,3]
]
最短路径就是2 + 3 + 5 + 1 = 11。

---

 

题目思路：

　　直接求出所有的自顶向下路径。ans [i][j] = min(ans[i-1][j],ans[i- 1][j + 1]) + triangle[i][j]。

---

 

代码（python）：

　　

class Solution(object):def minimumTotal(self, triangle):""":type triangle: List[List[int]]:rtype: int"""size = len(triangle)if size == 0:return 0ans = [triangle[0][0]]i = 1while i < size:tmp = []for j in range(len(triangle[i]) - 1):if j == 0:tmp.append(ans[0] + triangle[i][j])else:tmp.append(min(ans[j],ans[j-1])+triangle[i][j])tmp.append(ans[-1] + triangle[i][-1])ans = tmp[:]i += 1minans = ans[0]for i in ans:if i < minans:minans = ireturn minans