原题地址
https://leetcode.com/problems/triangle/description/
题意
想象一个杨辉三角那样的三角形（是指形状，数字可以自己输入），从三角形的顶点开始每次往左下方或右下方移动，一直到最底层，把经过的元素相加，求这个过程的和的最小值。
思路
动态规划，建表，dp[i][j]表示到triangle[i][j]这个元素时的最小和。
代码
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
if(n==0) return 0;
vector<vector<int> > dp(n, vector<int>(n, 0));
dp[0][0] = triangle[0][0];
for (int i = 1 ; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) {
dp[i][j] = triangle[i][j] + dp[i - 1][j];
} else if (j == i) {
dp[i][j] = triangle[i][j] + dp[i - 1][j - 1];
} else {
dp[i][j] = triangle[i][j] + min(dp[i - 1][j], dp[i - 1][j - 1]);
}
}
}
int result = dp[n-1][0];
for (int i = 0 ; i < n; i++) {
if (dp[n - 1][i] < result) {
result = dp[n - 1][i];
}
}
return result;
}
};
