从底部往上算，递归公式:
- dp(i,j) 表示从tri[i][j]到底部位置的最小的sum。
- dp(i,j) = min{ dp(i+1,j), dp(i+1,j+1) } + tri[i][j], 注意边界。
- ans = dp(0,0)
#include<vector>
#include<algorithm>
#include<cstdio>
#include <unordered_map>
#include <cmath>
#include <string>
using namespace std;
class Solution {
private:
int min(int a, int b)
{
return a < b? a : b;
}
public:
int minimumTotal(vector<vector<int>>& triangle) {
int row = (int)triangle.size();
for (int i = row - 2; i>=0; i--)
{
for (int j = 0; j <= i; j++)
{
triangle[i][j] += min(triangle[i+1][j+1], triangle[i+1][j]);
}
}
return triangle[0][0];
}
};
