Leetcode 120. 三角形最小路径和

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

例如，给定三角形：

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

说明：

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

解法1：二维dp, 自顶向下，时间复杂度和空间复杂度都是O(n^2)

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.size()<=0) {
            return 0;
        }
        vector<vector<int>> dp;
        for (int  i = 0; i < triangle.size(); i++)
        {
            vector<int> temp;
            for (int j = 0; j < triangle[i].size(); j++)
            {
                if(i==0) {
                    temp.push_back(triangle[i][0]);
                } else if(j == 0) {
                    temp.push_back(dp[i-1][j]+triangle[i][j]);
                } else if(j ==triangle[i].size()-1) {
                    temp.push_back(dp[i-1][j-1]+triangle[i][j]);
                } else {
                    temp.push_back(min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j]);
                }
            }
            dp.push_back(temp);
        }
        int minPath=INT32_MAX;
        int len=dp.size();
        for (int i = 0; i < dp[len-1].size(); i++)
        {
            if(dp[len-1][i]<minPath) {
                minPath=dp[len-1][i];
            }
        }
        return minPath;
    }
};

解法2：动态规划，自底向上，时间复杂度O(n^2), 空间复杂度O(n).

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.size()<=0) {
            return 0;
        }
        vector<int> dp=triangle[triangle.size()-1];
        for (int  i = triangle.size()-2; i >=0; i--)
        {
            for (int j = 0; j < triangle[i].size(); j++)
            {
                dp[j]=min(dp[j],dp[j+1])+triangle[i][j];
            }
        }
        return dp[0];
    }
};