这道题的思路可以参考前面的两道题：32. Pascal’s Triangle 和 38. Minimum Path Sum
其共同点都是用到了 DP 的思想。
DP, 即动态规划，的本质在哪？一句话：“前事不忘后事之师”。说白了，就是善于积累，不做重复劳动。
杨辉三角，下一行来自上一行的积累；最小路径，每一格基于左上两格的判断。
这道题，求依然是最小路径，所以还是积累的问题。
我们从例子开始分析，我们希望：每向下一行，能够使得下一行的元素成为他们能够成为最小的路径和，如何理解？
[2] -> [3,4] : [5,6]
[3,4] -> [6,5,7] : [9, 8, 11]
// 可以发现一个基本规律，即 front 和 back 前后两个元素是没得选的，他们的路径和来自上一个 vector 的首尾。
// 而中间的元素，可选择的公式为：
v[i] += min(steps[i-1], steps[i]); // v 代表下一行的 vector, steps 代表上一行累计过的 vector.而我们想要的最小路径和，就是迭代完整个三角形之后 steps 中最小的那个值。
代码非常简单。 不赘述了。
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
vector<int> steps;
for (auto &v : triangle) {
if (!steps.empty()) {
v.front() += steps.front();
v.back() += steps.back();
}
for (size_t i=1; i<steps.size(); ++i)
v[i] += min(steps.at(i-1), steps.at(i));
steps = v;
}
return *min_element(steps.cbegin(), steps.cend());
}
};