礼物的最大价值（medium）
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示：
0 < grid.length <= 2000 < grid[0].length <= 200
解题思路
还是依旧按照我们的五部曲来！
- 状态表示
- 按照 “经验 + 题目要求”，我们还是遵循以
dp[i][j]结尾，然后巴拉巴拉的情况哈哈 - 所以结合题目可以设定
dp[i][j]表示到达 [i, j] 位置时的礼物最大价值
- 按照 “经验 + 题目要求”，我们还是遵循以
- 状态转移方程
- 我们根据一个经验：从最近的一步入手。可以看到题目要求只能向右和向下走，也就是说当前位置 [i, j] 是与 [i-1, j] 和 [i, j-1] 位置处有关系！
- 通过状态表示，我们可以清楚得到左边或者上面格子的礼物价值也是最大的，那么我们只要选出它们两个其中最大的那个，然后加上当前位置处的礼物价值，即为当前位置的礼物最大价值！
- 即状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + gift[i-1][j-1]（至于这里为什么 gift 数组是下标减一，这和我们初始化是有关系的，请看下面！
- 初始化
- 因为我们在更新 dp 数组的时候，需要用到上面和左面格子，所以势必会有越界问题，所以还是一样，我们 开一行一列的虚拟位置，这个时候就需要关注两个问题：
- 保证让非虚拟位置的数据更新正确，所以虚拟位置的值要选好
- 下标的映射关系
- 这道题我们只需要 让虚拟位置都设为 0 即可，因为对于非虚拟位置的第一行和第一列来说，它们并不需要依赖于左上角的礼物价值，所以这道题的虚拟位置其实功能就很单一，就是为了防止越界！
- 因为我们在更新 dp 数组的时候，需要用到上面和左面格子，所以势必会有越界问题，所以还是一样，我们 开一行一列的虚拟位置，这个时候就需要关注两个问题：
- 填表顺序
- 从上往下，从左往右
- 返回值
- 因为我们需要的是右下角的值，所以返回 dp 表的右下角的值即可！
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); // 多开一行一列作为虚拟位置
for(int i = 1; i <= m; ++i)
{
for(int j = 1; j <= n; ++j)
{
// 状态转移方程
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
}
}
return dp[m][n];
}
};
4、下降路径最小和（medium）
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
示例 1：
输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：如图所示，为和最小的两条下降路径
示例 2：
输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：如图所示，为和最小的下降路径
提示：
n == matrix.length == matrix[i].length1 <= n <= 100-100 <= matrix[i][j] <= 100
解题思路
关于这⼀类题，由于我们做过类似的，因此「状态表示」以及「状态转移」是比较容易分析出来的。比较难的地⽅可能就是对于「边界条件」的处理。但其实只要弄明白了，那也不是很难！
首先就是状态表示，还是一样，我们以 dp[i][j] 结尾，然后巴拉巴拉。根据题目要求， dp[i][j] 表示到 [i, j] 位置处，此时下降路径最小和。
接着就是状态转移方程，题目说可以从某个位置处的 左上方、正上方、右上方 走到当前位置，所以我们当前位置就和这三个位置有关！以左上方为例，它走到当前位置的下降路径最小和，就是左上角位置的下降路径最小和加上当前位置数值，也就是说 dp[i][j] = dp[i-1][j-1] + matrix[i][j]，而对于正上方以及右上方都是一样的！
现在我们要取从上一个位置来的下降路径最小和，其实就是取上面三个位置的最小值，然后加上当前位置的数值即可！
状态转移方程：dp[i][j] = max(dp[i-1][j-1] , dp[i-1][j], dp[i-1][j+1]) + matrix[i][j]
然后就是初始化问题了，很显然，为了防止越界问题的麻烦，我们添加虚拟行列，但这次和上面题目的区别就是这道题 需要多加两列，而不是加一列，因为这次我们当前位置的最近一步涉及到了三个位置，最后一个位置可能也会越界！
所以我们就多加一行和两列作为虚拟位置，如下图：
并且还要注意到的是，我们不能简简单单的说给虚拟行列都初始化为 0，仔细想一下，虽然非虚拟位置的第一行需要的就是原来的路径大小，也就是第一行虚拟位置设为 0 没问题，但是下面的虚拟行列呢❓❓❓
假设设为 0，那么看上图中的最后一行的红色星号位置，如果假设它的左上角是 0，那么如果此时它的正上方和右上方都大于 0，那么此时就错了，因为就会取到这个原本不应该被处理的 0，因为它只是作为边界。
所以为了防止这种会被取到的情况，我们 将除了第一行虚拟位置以外的其它虚拟位置，都设为 INT_MAX，这样子就保证不会影响到其对正确路径的获取情况了！对于其它的边界点情况也是如此！
接着就是填表顺序，很明显，要遍历整个表，所以要从上到下，从左往右去填。
最后就是返回值，因为我们的最小结果在最后一行，所以我们需要去 遍历最后一行查找最后一行的最小值返回即可！
class Solution {
public:
int getMin(int a, int b, int c) // 求最小值
{
a = min(a, b);
a = min(a, c);
return a;
}
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();
vector<vector<int>> dp(n+1, vector<int>(n+2, INT_MAX)); // 多开两列，并且全部都初始化为INT_MAX
for(int i = 0; i <= n+1; ++i) // 将第一行初始化为0
dp[0][i] = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
// 状态转移方程
dp[i][j] = getMin(dp[i-1][j], dp[i-1][j-1], dp[i-1][j+1]) + matrix[i-1][j-1];
}
}
// 返回最后一行的最小值
int tmp = INT_MAX;
for(int i = 1; i <= n; ++i)
{
tmp = min(dp[n][i], tmp);
}
return tmp;
}
};