三角形最小路径和

题目：

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

示例：

输入：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

解题方法：

中等题果然难度就是不一样了，之前做数组题想想总会有个大概思路，现在不看题解完全不知道怎么做，看了题解还是不知道怎么做！难哟。
这道题原本我想通过自顶向下进行动态规划求解，本来也不是很懂动规，不确定递推过程中最优子问题是不是全局最优，最后提交就错了。看了题解以后思路稍微清晰了一点，这道题还是要老老实实的遍历，不过是自底向上遍历，另外还要进行原地修改，这样可以降低内存的使用：

• 从倒数第二层开始，依次遍历每一个元素，并求解该元素的最小路径，递推公式：
  triangle[i][j]=min(triangle[i+1][j],triangle[i+1][j+1])+triangle[i][j]，原地修改最小路径；
• 第一层也就是最后得到的最小路径。

代码和结果：

class Solution {
public:
    int min(int a,int b)
    {
        return a<b?a:b;
    }
    int minimumTotal(vector<vector<int>>& triangle) {
        int n=triangle.size();
        for(int i=n-2;i>=0;i--)
        {
            for(int j=0;j<triangle[i].size();j++)
            {
                triangle[i][j]=min(triangle[i+1][j],triangle[i+1][j+1])+triangle[i][j];
            }
        }
        return triangle[0][0];
    }
};

运行结果:

原题链接：https://leetcode-cn.com/problems/triangle/