力扣120. 三角形最小路径和（动态规划）
动态规划
从三角形的底部开始转移，到顶部结束；转移方程：初始化条件，初始化底部的值：
复杂度分析
时间复杂度：O(n^2)，其中 n 是三角形的行数。空间复杂度：O(n^2)。我们需要一个 n*n 的二维数组存放所有的状态。
//
// main.cpp
// 120minimumTotal
//
// Created by MXQ on 2020/10/21.
//
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
if (triangle.size()==0) {
return 0;
}
if (triangle.size()==1 && triangle[0].size()==0) {
return 1;
}
if (triangle.size()!=1 && triangle[0].size()==0) {
return 0;
}
int n=triangle.size();
vector<vector<int>>f(n,vector<int>(n));
for (int i=0; i<n; i++) {
f[n-1][i]=triangle[n-1][i];
}
for (int i=n-2; i>=0; i--) {
for (int j=0; j<=i; j++) {
f[i][j]=min(f[i+1][j],f[i+1][j+1])+triangle[i][j];
}
}
return f[0][0];
}
};
int main(int argc, const char * argv[]) {
// insert code here...
Solution s;
vector<int>triangle1={2};
vector<int>triangle2={3,4};
vector<int>triangle3={6,5,7};
vector<int>triangle4={4,1,8,3};
vector<vector<int>> triangle={triangle1,triangle2,triangle3,triangle4};
auto result=s.minimumTotal(triangle);
std::cout << result<<endl;
std::cout << "Hello, World!\n";
return 0;
}
