难度中等351
在一个 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
1、深度优先遍历DFS
这种方法在这道题是会超出时间限制的，但是如果不考虑时间复杂度，那么同样是可以通过的！
class Solution {
public:
void val(vector<vector<int>>& grid, int i, int j, int tmp)
{
// 出界则返回
if(i >= grid.size() || (j >= grid[i].size()))
return;
// 到达右下角后更新最大值
if((i == grid.size() - 1) && (j == grid[i].size() - 1))
{
n = max(n, tmp);
return;
}
// 继续递归到右面或者下面方格
val(grid, i+1, j, tmp + grid[i][j]);
val(grid, i, j+1, tmp + grid[i][j]);
}
int maxValue(vector<vector<int>>& grid)
{
val(grid, 0, 0, 0);
return n + grid[grid.size() - 1][grid[0].size() - 1]; // 最后返回的时候要加上右下角的结点值
}
private:
int n = 0;
};2、动态规划
仔细想一下，因为每次只能向右走和向下走，那么其实每一格要想得到最大值，那么就是它的左边和上边格的最大值，那么就很简单，只需要遍历一遍这个数组，将每次方格得到的最大值更新一下即可（在原数组操作，减少空间复杂度）！
状态方程为: grid[i][j] = max{grid[i-1][j], grid[i][j-1]} + grid[i][j] ，要注意的就是边界问题，因为可能是 i=0 或者 j=0 的情况，那么就要特殊处理一下边界！或者说可以将数组外围扩大一圈，用空间换来判断的安全性！
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
for(int i = 0; i < grid.size(); ++i)
{
for(int j = 0; j < grid[i].size(); ++j)
{
if(i == 0 && j == 0)
continue;
else if(i == 0 && j != 0)
{
grid[i][j] = grid[i][j-1] + grid[i][j];
}
else if(i != 0 && j == 0)
{
grid[i][j] = grid[i-1][j] + grid[i][j];
}
else
{
grid[i][j] = max(grid[i][j-1], grid[i-1][j]) + grid[i][j];
}
}
}
// 最后返回右下角的值即可！
return grid[grid.size()-1][grid[grid.size()-1].size()-1];
}
};