跳台阶问题的非递归解法

针对跳台阶问题，除了递归算法之外，这里提供一种新的解法。每次跳动距离无非1或2，跳的总距离为N。设跳动距离为1的次数为x，跳动距离为2的次数为y，则有x+2y=N，总的跳动次数为x+y。暂不考虑x和y取值为0的情况，则可选择的跳动方式有通常解nSol=(x+y)!/(x!*y!)。
当N=1时，只有x=1且y=0满足，故nSol=1。
当N>1时，y的可能取值为0:floor(N/2)。其中y=0表示每次跳动距离都为1，这是一种情形。y>0时，x有可能为0，此时N为偶数且每次跳动距离为2；如果y>0时x≠0，可用通常解计算跳动方案数。
MATLAB实现代码如下，输入总的跳动距离N，输出可选方案数目nSol。

function nSol = frogJump(N)
if N==1
nSol = 1;
elseif N>1
yMax = floor(N/2);
nSol = 0;
for y = 0:yMax
x = N - 2*y;
if y==0
nSol = nSol + 1;
continue;
end
if x~=0
nSol = nSol + factorial(x+y)/factorial(x)/factorial(y);
elseif x==0
nSol = nSol + 1;
end
end
end
end