在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

输入:

[

[1,3,1],

[1,5,1],

[4,2,1]

]

输出: 12

解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示：

0 < grid.length <= 200

0 < grid[0].length <= 200

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

动态规划经典题目！

这道题一开始是想用dfs做的。。然后发现就要不停地走回头路，然后就超时了。。之前做别的dfs题目时看见有大佬会用剪枝来解决问题，但这道题我实在没看出来哪里可以剪。。。

既然要走回头路，能不能每一步都计划好？

然后我想，能不能走一步看一步，结果看了看，自己想了个极端例子，走一步看一步的方法可取但是拿不到最大。

后来我想起来，小学有一个求最短路径的问题，也是要求不能走回头路，那个时候的方法是标个脚标，每个标都代表到达这个位置的最短路径。

所以这里也能记下每个点的最大礼物。

特殊情况三个，原点，0行，0列。原点不用处理，0行加第i-1列的值，0列加第i-1行的值。其它情况比较上一行和上一列的那个点哪个的礼物最大就选哪个。

class Solution {
public:int maxnum=0;int lx;int ly;int maxValue(vector>& grid) {lx=grid.size();ly=grid[0].size();for(int x=0;x

官解有一点说的很好，其它的信息都是无用的，我们需要保存的只有上一行和上一列同行的点，其它都是浪费空间，所以按官解做的可以再进行改进。

class Solution {
public:int maxnum=0;int lx;int ly;int maxValue(vector>& grid) {lx=grid.size();ly=grid[0].size();int tmp[ly];for(int x=0;x

我的方法，空间超过94%，官解，81%。。。。。

再看的时候忽然发现我是就着grid改了，这不更省吗。。。