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.

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).

分析：

也是一道典型的坐标型动态规划，初始化比较有意思，需要初始化第一列和对角线。循环的时候注意第二层j = 1; j < i，这是因为只需要用到半个n-by-n的vector。严格的说这是浪费了空间的。

解法：

class Solution {
public:
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    int minimumTotal(vector<vector<int> > &triangle) {

        if (triangle.size() == 0) {
            return 0;
        }
        if (triangle[0].size() == 0) {
            return 0;
        }

        int n = triangle.size();
        vector<vector<int> > pathSum(n, vector<int>(n, INT_MAX) );

        pathSum[0][0] = triangle[0][0];
        for (int i = 1; i < n; i++) {
            pathSum[i][0] = pathSum[i - 1][0] + triangle[i][0];
            pathSum[i][i] = pathSum[i - 1][i - 1] + triangle[i][i];
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < i; j++) {
                pathSum[i][j] = min(pathSum[i - 1][j - 1], pathSum[i - 1][j]) + triangle[i][j];
            }
        }

        int result = INT_MAX;
        for (int i = 0; i < n; i++) {
            result = min(result, pathSum[n - 1][i]);
        }
        return result;
    }
};