斐波拉契(算法)

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

思路:逆向思维 ;如果我从第n个台阶进行*阶,下一步有2中可能,一种走到第n-1个台阶,一种是走到第n-2个台阶。

           即 F(n) = F(n-1)+F(n-2);

pubulic int Jump(int k){
    
    if(k==0)
        return 0;
    if(k==1)
        return 1;
    
    int slow = 1;
    int fast = 1;
    int res = 0;  
    
    for(int i=2;i<=k;i++){
        res = slow + fast;
        slow = fast;
        fast = res;
    }
    return res;
}

 

上一篇:如何判断链表中是否有环并找出环的入口位置


下一篇:剑指offer(C++)-JZ22:链表中倒数最后k个结点(数据结构-链表)