[LeetCode]Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

今天的最后一题Triangle是经典的动态规划问题，第i行第j个节点接收来自第i-1行第j-1个节点和第j个节点的消息，计算出到达自己的最短路径，再将消息向下层传播。需要两个数组，一个记录上一行的路径长度，一个计算当前行的路径。

代码

class Solution {
public:
    const int INF=100000;
    int minimumTotal(vector<vector<int> > &triangle) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int n = triangle.size();
        // 若triangle为空，返回0
        if(n==0)
            return 0;
        
        vector<int> prev_sum = triangle[0];
        vector<int> cur_sum;
        for(int i=1; i<n; ++i)
        {
            int rnum = triangle[i].size(); // number of elements in a row
            for(int j=0; j<rnum; ++j)
            {
                int left = j>0?prev_sum[j-1]:INF; //最左侧节点和最右侧节点的处理
                int right = j<rnum-1?prev_sum[j]:INF;
                int cur = left<right?left:right;
                cur += triangle[i][j]; // 计算从根节点到此节点的最短路径
                cur_sum.push_back(cur);
            }
            prev_sum = cur_sum;
            cur_sum.clear();
        }
        // 在三角形底部找到最小路径值
        int minpath = prev_sum[0];
        for(int i=1; i<n; ++i)
            minpath = prev_sum[i]<minpath?prev_sum[i]:minpath;
            
        return minpath;
    }
};