leetcode 120. 三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
题解：
1.一个三角形矩阵
2.从第一层开始每层选一个相邻数
3.走到最底层，走过的路径上的和为所有路径最小
例如，给定三角形：
[[2],
[3,4],
[6,5,7],
[4,1,8,3]]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
解题思路：
-
对于一层上的数，每个数都可能成为结果路径上的点
-
但对于一层上的元素，其下层路径必须是下标相同的位置或+1的位置
-
采用自底向上走的方式，设置一个临时数组记录处理每层节点时，对每种可能的路径累计一个和，当前遍历元素，从下层相同下标和下标+1元素取较小值，与当前元素累计和，直到回到最顶层元素时，在临时数组头部也累计出最小路径和
C/C++题解：
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
vector<int> dp(triangle.size() + 1,0);
for(int i=triangle.size() -1;i>=0;i--){
for(int j=0;j<triangle[i].size();j++){//自底向上计算
//对于当前元素，比较它下一层相同位置和+1位置，用小值加当前元素
//每完成一次内循环，即处理完该层以下的最小路径和
dp[j] = min(dp[j],dp[j+1]) + triangle[i][j];}}
return dp[0]; }};
Debug结果：
Java题解：
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int[] dp = new int[triangle.size() +1];
for(int i=triangle.size() -1;i>=0;i--){
for(int j=0;j<triangle.get(i).size();j++){//自底向上计算
//对于当前元素，比较它下一层相同位置和+1位置，用小值加当前元素
//每完成一次内循环，即处理完该层以下的最小路径和
dp[j] = Math.min(dp[j],dp[j+1]) + triangle.get(i).get(j);} }
return dp[0];}}
Debug结果：
Python题解：
class Solution(object):
def minimumTotal(self, triangle):
""":type triangle: List[List[int]]:rtype: int"""
dp = [0] * (len(triangle) + 1)
for i in range(len(triangle)-1, -1, -1):
for j in range(len(triangle[i])): #自底向上计算
#对于当前元素，比较它下一层相同位置和+1位置，用小值加当前元素
#每完成一次内循环，即处理完该层以下的最小路径和
dp[j] = min(dp[j],dp[j+1]) + triangle[i][j]
return dp[0]
Debug结果：
更多题解移步公众号免费获取