题目描述

教练我也想学这个！在一个n*n的正方形训练场上中下标从1-n，每个位置都有一枚硬币，小明从起点出发，跳跃可以先向右走一步，再向上或向下走两步，或者先向右走两步，再向上或向下走一步。但是小明不能跳出训练场，也不能往回跳，不然会遭到教练的严厉表扬。小明左上位置(1,1)上，他想在完成训练获得更多的硬币买快乐水。身为教练的你要帮他吗？

思路：动态规划

首先，观察本题的跳跃方式，有一个共性特点：只会向右跳跃

对于每个位置，我们需要考虑四种跳跃方式：先向右走一步，再向上或向下走两步，或者先向右走两步，再向上或向下走一步。

我们可以定义长度为4的方向数组，来表示这四种跳跃方式

定义$f[i][j]$表示到达$(i,j)$点的最大硬币数量，那么我们可以枚举$(i,j)$是由上述哪一种方式跳跃得到的