三角形最短路径

基本思想是自底向上，但是又可以细分为两种方法：

1. 空间复杂度O(n)，优点是无需修改输入
2. 空间复杂度O(1)，优点是无需辅助空间

方法一

//
// Created by jt on 2020/8/14.
//
#include <vector>
using namespace std;

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

方法二

//
// Created by jt on 2020/8/14.
//
#include <vector>

using namespace std;

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