看到这样的题目，理所当然先想到的方法就是递推，但是该怎么推呢？ 这个矩阵是对称的，那么我们只有计算四分之一的部分就可以了(对称)。 我们先定义三个数组， `F[]` , `G[]` 和 `L[]` 。 * `F[]` 数组所存的是 $2*n$ 格子所有走法的数量。 * `G[]` 数组所存的是含有顶点那部分的那个格子为起点的所有走法的数量。 * `L[]` 数组所存的是 `2` 的所有次方的结果。 然后此题的关键部分就是一点：我们可以发现每列都只有 `2` 个格子，所以当你往左边走的时候，如果右边还有格子，那么你就只能一列走一格，不然回不到后边，如果不理解这一点就仔细想想，自己模拟一下就知道了。往右边同理。 既然理解了上面这一点，在这里我就直接讲推出后的过程了，以当前格子 $2*n(n>3)$ 为例。 首先我们取最坐上角的那个格子为起点，那么此点的走法有三种： 1、往下走，那么走法数= $2*g[n-1]$ 。 2、往右走再往左走，那么走法数= $2*2*g[n-2]$ 。 3、往右走再往右走(最后回到最左端)，那么走法数= $L[n-1]$ 。 接下来我们取除上种情况的其他任意一个格子为例。 假设我们取的格子位置是：他的左边有x个格子，右边有 `n-1-x` 个格子。 则，走法只有两种： 1、第一步往左走，那么他只能走完左边的才能走右边的。走法数= $L[x]*2*g[n-1-x]$ 。 2、第一步往右走，那么他只能走完右边的才能走左边的。走法数= $L[n-1-x]*2*g[x]$ 。