题目：
给定一个数字三角形，找到从顶部到底部的最大路径和。每一步可以移动到下面一行的相邻数字上。输入第一行数字n是三角形的行数，接下来的n行是数字三角形的每一行，如：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出是 30
思路：
1、递归+记忆法
用二维数组存储数字三角形中的每一行，不难发现，每个数字的节点nums[i][j]在扫描的过程当中都有两条可选路经（nums[i + 1][j]和nums[i + 1][j + 1]），所以可以把它看成是二叉树。类似二叉树的遍历，递归进行每个节点进行遍历，得到的值加上当前节点的值，取其较大者。在递归的过程中有重复计算的部分，比如在计算nums[2][0]的过程中计算了nums[3][1]，而在计算nums[2][1]的过程中也计算了nums[3][1]，所以可以用一个辅助数组将每次计算的值存储在visited[i][j]中，每次递归进去之后先判断是否在visited数组中，如果在则直接返回visited数组中的值，否则再递归计算。这样减少了递归的次数，大大节省了时间。
2、动态规划
由题可以得到递推式result[i][j] = max(nums[i + 1][j], nums[i + 1][j + 1]) + nums[i][j]。由自低向上进行编程（最后一行每一个元素的最优解就是本身），递推出每一个节点所能得到的最优解，然后result[0][0]的值就是所要求得的解。在这里为了节省内存，将nums数组和result数组使用同一个数组（即在nums数组中直接用每个节点的最优解替换原数值）。
代码：
1、递归+记忆法
class Solution {
public:
int longestOfPath(std::vector<std::vector<int>> &nums, int i, int j) {
if (nums.size() == 0) {
return 0;
}
std::vector<std::vector<int>> visited;
for (auto &a : nums) { //初始化记忆化数组
std::vector<int> tmp(a.size(), INT_MIN);
visited.push_back(tmp);
}
return longestOfNumber(nums, i, j, visited);
}
private:
int longestOfNumber(std::vector<std::vector<int>> &nums, int i, int j, std::vector<std::vector<int>> &visited)
{
if (nums.size() == i + 1) {
return nums[i][j];
}
if (visited[i][j] != INT_MIN) {
return visited[i][j];
}
int a = longestOfNumber(nums, i + 1, j, visited); //左边
int b = longestOfNumber(nums, i + 1, j + 1, visited); //右边
int result = maxNum(a, b) + nums[i][j]; //计算结果
visited[i][j] = result; //保存进记忆化数组
return result;
}
inline int maxNum(int a, int b)
{
return a > b ? a : b;
}
};2、动态规划
class Solution {
public:
int longestOfPath(std::vector<std::vector<int>> &nums)
{
for (int i = nums.size() - 2; i >= 0; --i) { //从倒数第二行开始递推（倒数第一行每个节点的最优解是本身）
for (int j = 0; j < nums[i].size(); ++j) {
nums[i][j] = (nums[i + 1][j] > nums[i + 1][j + 1] ? nums[i + 1][j] : nums[i + 1][j + 1]) + nums[i][j];
}
}
return nums[0][0];
}
};