三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

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

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、解题方式（递归+备忘录法）

缺点是空间复杂度高，时间也不高
自上向下的计算
直接递归无法满足时间需求，备忘录法可以减少重复操作，同时也增加了空间需求

class Solution {
public:
    vector<vector<pair<int, bool>>> arr;
    int minimumTotal(vector<vector<int>>& triangle) {
        for(int i = 0; i < triangle.size(); ++i) {
            vector<pair<int, bool>> temp;
            for(int j = 0; j < triangle[i].size(); ++j) {
                pair<int, bool> node(0, false);
                temp.push_back(move(node));
            }
            arr.push_back(temp);
        }
        return dfs(triangle, 0, 0 ,0);
    }
    
    int dfs(const vector<vector<int>>& tri, int k, int i, int j) {
        if(k == tri.size() - 1) {
            return tri[i][j];
        }
        int left = INT_MAX;
        if(arr[i+1][j].second) {
            left = arr[i+1][j].first;
        } else {
            left = dfs(tri, k + 1, i + 1, j);
            arr[i+1][j].first = left;
            arr[i+1][j].second = true;
        }
        int right = INT_MAX;
        if(arr[i+1][j+1].second) {
            right = arr[i+1][j+1].first;
        } else {
            right = dfs(tri, k + 1, i + 1, j + 1);
            arr[i+1][j+1].first = right;
            arr[i+1][j+1].second = true;
        }
        int min = left < right ? left : right;
        return min + tri[i][j];
    }
};

二、二维数组的动态规划

自底向上的计算方法

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int **dp = new int* [triangle.size()];
        for(int i = 0; i < triangle.size(); ++i) {
            dp[i] = new int[triangle[i].size()];
        }
        for(int i = 0; i < triangle.back().size(); ++i)
            dp[triangle.size() - 1][i] = triangle.back()[i];
        for(int i = triangle.size() - 2; i >= 0; --i) {
            for(int j = 0; j < triangle[i].size(); ++j) {
                dp[i][j] = (dp[i+1][j] < dp[i+1][j+1] ? dp[i+1][j] : dp[i+1][j+1]) + triangle[i][j];
                // cout<<"i = "<<i<<"  j = "<<j<<" dp = "<<dp[i][j]<<endl;
            }
        }
        return dp[0][0];
    }
};