1. 120

triangle

2. 算法

http://www.cnblogs.com/grandyang/p/4286274.html

O(n^2)

• 设状态是f(i,j),表示从位置(i,j)出发，路径的最小和，状态转移方程是：

• f(i,j)=min{f(i,j+1),f(i+1,j+1)}+(i,j)

• (i,j)表示原三角形第i行j列的值

在原数组上修改

3. 代码

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

    }
};