程序员社区

【数据结构与算法】青蛙跳台阶问题解析

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

因为n级台阶,第一步有n种跳法:跳1级、跳2级、到跳n级 跳1级,剩下n-1级,则剩下跳法是f(n-1) 跳2级,剩下n-2级,则剩下跳法是f(n-2) 所以f(n)=f(n-1)+f(n-2)+...+f(1) 因为f(n-1)=f(n-2)+f(n-3)+...+f(1) 所以f(n)=2*f(n-1)

【数据结构与算法】青蛙跳台阶问题解析插图

如果target = 0,说明是直接跳过来,否则返回1;否则,总是有target中选择,把每种选择包含的步骤起来就行了,递归到0结束循环,并合并结果。

public int JumpFloorII(int target) {
        if(target == 0 ){
      return 1;
     }
     int count = 0
     for(int i = 1; i<target;i++){
        count += jumpFloorII(target - i);
     }
      return count;
     }
    }
赞(0) 打赏
未经允许不得转载:IDEA激活码 » 【数据结构与算法】青蛙跳台阶问题解析

相关推荐

  • 暂无文章

一个分享Java & Python知识的社区