乍一看，这道题似乎与经典递推(dp)过河卒很像。可是仔细看，过河卒中的棋子可以向下或向右，而方格取数中的小熊可以向下、向右，还可以向上。
这意味着什么？
意味着对于每一个点，小熊可能是从下面过来的，也可能是从上面过来的，如图：
小熊既可以从红色路径抵达灰点，也可以从蓝色路径抵达灰点。
我们不知道小熊抵达某一个点是从上面，下面，或者左边过来的。因此，不能使用过河卒的方法推导。那怎么办呢？
将储存答案的数组增加一个维度。
设 f[i][j][k] 表示小熊走到 点(i,j)(i,j)(i,j) 时能取到的最大整数和。
其中，kkk表示小熊到达这个点的方式。0表示小熊从这个点的下方过来，1表示小熊从这个点的上方过来。从左边过来的路径单独考虑，不需要专门为其赋一个kkk值。从左边来的路径已经包含在从上方或下方来的路径中。
这样，小熊的路像高架桥一样彼此错落开，路径就显得清晰了。
本题答案较大,要开 LONG LONG
我们采用记忆化搜索的方式，搜索一遍最大值。基本思想如下：
因为要求最大值，所以先将f数组赋值为一个最小值MIN（定义MIN=(-1)*2e18）
题难则反，如果从(1,1)(1,1)(1,1)开始搜索有点困难，那就运用逆向思维，从(n,m)(n,m)(n,m)开始搜索。
初始条件：走到点(1,1)(1,1)(1,1)的最大值只能为a[1][1]。因此，将 f[1][1][0] 和 f[1][1][1] 都赋为a[1][1]。
建立函数 search(int x,int y,int k) ，表示到达以kkk方式到达点(x,y)(x,y)(x,y) 的最大值。
* 若 (x,y)(x,y)(x,y) 超出 nnn x mmm 的方格范围，无解，返回MIN。
* 若 f[x][y][k] 不为MIN（即已经搜索到最大值），返回f[x][y][k]。
* 若k==0（从下方来），那就往下搜索，顺藤摸瓜寻找最大值。此时，小熊可能从下方来，也可能从左边来。而从左边来包含：从左边的上方来，从左边的下方- 来。因此，有三种情况需要搜索并取最大值：从正下方来，从左上方来，从左下方来。
* 若k==1（从上方来），那就往上搜索。同上，有三种情况需要搜索并取最大值：从正上方来，从左上方来，从左下方来。
由此可见，答案即为search(n,m,1)。
（此处k==1是因为(n,m)(n,m)(n,m)只能从上方或左边来，不能从下方来）
因为我们每次都把搜索得到的最大值存在f[x][y][k]，所以每个点都只需要搜一遍，时间复杂度O(nm)O(nm)O(nm)，可以AC。
AC代码
欢迎加入团队
