120 - Triangle

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).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
Hide Tags
Array Dynamic Programming


首先想到的是递归，每次到达底层计算当前路径的和，跟踪最小的即可。
调用栈的空间占用满足要求，但是严重超时。

按照提示用DP重写，需要一个大小为行数的buffer。
实际上buffer的大小是按最后一行的个数来说的，只不过也等于行数，所以也合乎要求。
在这个buffer里不断计算每个位置能获得的最好sum，状态方程还是比较简单的，
首尾只能继承加上自己，中间的去左上右上小的一个加上自己，同时跟踪行内最小sum，
全部算完就可以得到结果了， DP跑出来 8ms。
把超时的case拿来跑了，DP瞬间算完，递归算了很久，很久，还没完……，睡了。

class Solution {
public:
    //DP
    int minimumTotal(vector<vector<int>>& triangle) {
        int sz=triangle.size(), sum=0, mini=0;
        if(sz)
        {
            int zz= triangle[0].size();
            if(zz)
            {
                int* buf = new int[sz];
                memset(buf, 0, sz*sizeof(int));
                for(int ii=0; ii<sz; ++ii)
                {
                    mini=INT_MAX;
                    for(int jj=ii; jj>=0; jj--)
                    {
                        if(0==jj)
                            buf[jj] = triangle[ii][jj] + buf[jj];
                        else if(ii==jj)
                            buf[jj] = triangle[ii][jj] + buf[jj-1];
                        else
                            buf[jj] = triangle[ii][jj] + min(buf[jj-1], buf[jj]);

                        if(mini>buf[jj])
                            mini = buf[jj];
                    }
                }
                if(buf)
                    delete[] buf;
            }
        }       
        return mini;
    }

    //recursive, time out
    int minimumTotal_recursive(vector<vector<int>>& triangle) {
        int sz=triangle.size(), sum=0, min;
        if(sz)
            getMinSum(triangle, 0, 0, sum, min);
        return min;
    }
   
    void getMinSum(vector<vector<int>>& array, int level, int index, int& sum, int& min)
    {
        //update sum with my value
        int val = (array[level])[index];
        sum += val;

        //if this is bottom, check and update min, which is final result, then return;
        if(level==(array.size()-1))
            min = (min > sum)?sum:min;
        else
        {
            //recursive call for left child
            getMinSum(array, level+1, index, sum, min);
       
            //recursive call for right child
            getMinSum(array, level+1, index+1, sum, min);
        }
        sum -= val;
        return;
    }
};

DP 8 ms.