// 分治法——借助上面转化的二叉树理解
int rMinimumTotal(vector<vector<int>>& triangle, int x, int y, int height){
if(x == height){
return 0;
}
return min(rMinimumTotal(triangle, x + 1, y, height),
rMinimumTotal(triangle, x + 1, y + 1, height)) + triangle[x][y];
}
int minimumTotal(vector<vector<int>>& triangle) {
int height = triangle.size();
return rMinimumTotal(triangle, 0, 0, height);
}
方法二：记忆化搜索——优化 DFS，缓存已经被计算的值（空间换时间），本质上是动态规划
动态规划就是把大问题变成小问题，并解决了小问题重复计算的方法称为动态规划。
动态规划和 DFS 区别
二叉树 子问题是没有交集，所以大部分二叉树都用递归或者分治法，即 DFS，就可以解决
像 triangle 这种是有重复走的情况，子问题是有交集，所以可以用动态规划来解决
可以用二维数组，可以借助一维数组（长度为三角形的行数），也可以原地操作
// 自底向上
int minimumTotal(vector<vector<int>>& triangle) {
vector<vector<int>> hash;
vector<int> rHash;
int len = triangle.size() - 1;
for(int i = len;i >= 0; i--){
for(int j = 0; j < i + 1;j++){
if(i == len){
rHash.push_back(triangle[i][j]);
}else{ // hash[len-i-1][j + 1], hash[len-i-1][j]这就是相邻的节点的坐标
rHash.push_back(min(hash[len - i - 1][j + 1],
hash[len - i - 1][j]) + triangle[i][j]);
}
}
hash.push_back(rHash);
rHash.clear();
}
return hash[len][0];
}
const int prime = 1e9 + 7;
long long getSolutions(int n, int m, int k, int p) {
vector<vector<long long>> solutions(k + 1, vector<long long>(n + 2));
// base case
for (int i = 0; i < n + 2; ++i) {
solutions[0][i] = 0;
}
solutions[0][m] = 1;
for (int i = 1; i < k + 1; ++i) {
for (int j = 1; j < n + 1; ++j) {
solutions[i][j] = solutions[i - 1][j - 1] + solutions[i - 1][j + 1];
solutions[i][j] %= prime;
}
}
return solutions[k][p];
}
long long getSolutions(int n, int m, int k, int p) {
vector<long long> curr(n + 2);
vector<long long> last(n + 2);
// base case
for (int i = 0; i < n + 2; ++i) {
last[i] = 0;
}
last[m] = 1;
for (int i = 1; i < k + 1; ++i) {
for (int j = 1; j < n + 1; ++j) {
curr[j] = last[j - 1] + last[j + 1];
curr[j] %= prime;
}
for (int j = 1; j < n + 1; ++j) {
last[j] = curr[j];
}
}
return curr[p];
}
