每日一题[2194]跳动的青蛙

已知青蛙从坐标平面原点出发跳动，当它位于坐标 $(x,y)$ 时可以跳动到 $(x+1,y),(x+2,y),(x,y+1),(x,y+2)$ 中的任意一个位置，则从 $(0,0)$ 出发跳到 $(4,4)$ 结束的所有不同的跳动方案数为_______．

答案    $556$．

解析    设 $N(a,b)$ 是从点 $(0,0)$ 出发到达 $(a,b)$（$a,b\in\mathbb Z$）的不同的跳动方案数，则 $N(0,0)=1$ 且当 $a,b<0$ 时，定义 $N(a, b)=0$．对满足 $a+b \geqslant 1$ 的非负整数 $a$ 和 $b$，有以下递推式 $$N(a, b)=N(a-1, b)+N(a, b-1)+N(a-2, b)+N(a, b-2).$$ 利用这个递推式可得所求的不同的跳动方案数有 $556$． $$\begin{array}{ccccccc} &5&20&71&207&556&(4,4)\\ &3&10&32&84&207&\\ &2&5&14&32&71\\ &1&2&5&10&20\\ (0,0)&1&1&2&3&5\\ \end{array}$$