跳台阶、跳台阶升级版(算法)

xiaoxiao2021-02-28  124

一出来跳台阶,我们要记住两个关键词:

一是递归、二是斐波那契数列。

简单版的跳台阶题目呈现如下:

每次能跳1阶或2阶,共10阶,问方法数?

直接给代码:

public int JumpFloor(int target) { if(target==1||) return target; else{ return JumpFloor(target-1)+JumpFloor(target-2); } } 升级版的跳台阶题目呈现如下:

每次能跳1~n阶,共n阶,问方法数?

(tip:这种问题可以先仿造上例给出递推式)

f(n)=f(n-1)+f(n-2)+......+f(2)+f(1);   --------①

f(n-1)=f(n-2)+f(n-3)+.......+f(2)+f(1);  -------②

由①②式:f(n)=2f(n-1);

故:f(n)=2^(n-1)*1=2^(n-1).

代码就可以这样写 

int count=1<<(n-1);

转载请注明原文地址: https://www.6miu.com/read-20753.html

最新回复(0)