相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

示例

[
     [2],
[3,4],
   [6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

/// Memory Search
/// Time Complexity: O(n^2)
/// Space Complexity: O(1)
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {

        int n = triangle.size();
        vector<vector<int>> dp(n, vector<int>(n, -1));
        for(int i = 0 ; i < n ; i ++)
            go(triangle, n - 1, i, dp);

        return *min_element(dp[n-1].begin(), dp[n-1].end());
    }

private:
    int go(const vector<vector<int>>& triangle, int i, int j,
           vector<vector<int>>& dp){

        if(dp[i][j] != -1)
            return dp[i][j];

        if(i == 0)
            return dp[i][j] = triangle[i][j];

        if(j == 0)
            return dp[i][j] = triangle[i][j] + go(triangle, i - 1, 0, dp);

        if(j == i)
            return dp[i][j] = triangle[i][j] + go(triangle, i - 1, i - 1, dp);

        return dp[i][j] = triangle[i][j] + min(go(triangle, i - 1, j - 1, dp),
                                               go(triangle, i - 1, j, dp));
    }
};
/// Dynamic Programming
/// Time Complexity: O(n^2)
/// Space Complexity: O(1)
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {

        int n = triangle.size();
        for(int i = 1 ; i < n ; i ++){

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

        return *min_element(triangle[n-1].begin(), triangle[n-1].end());
    }
};