美文网首页
剑指offer_6_1青蛙变态跳台阶

剑指offer_6_1青蛙变态跳台阶

作者: 韩who | 来源:发表于2020-01-21 10:16 被阅读0次

青蛙变态跳台阶

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

方法一:

公式推导

f(n) = f(n-1)+f(n-2)+f(n-3)+f(4)+....+f(0)

f(n-1) = f(n-2)+f(n-3)+f(4)+....+f(0)

代入 f(n) = 2*(f(n-2)+f(n-3)+f(4)+....+f(0)) = 2 * f(n-1)

public class Solution {
    public int JumpFloorII(int  n) {
          //将前面的总数加上去
        int sum = 2;
        if(n <= 2){
            return n;
        }
        else {
            for(int i = 3; i<=n;i++){
                 sum*=2;
            }
           
        }
        return sum;

    
    }
}

方法二:

递归

第一种跳 n 步,剩下0步

第二种跳 n-1 步,剩下1步需要跳的情况

第二种跳 n-2 步,剩下2步需要跳的情况

第二种跳 n-3 步,剩下3步需要跳的情况

第二种跳 n-4 步,剩下4步需要跳的情况

每个父问题都可以分解为子问题,递归

可以使用递归

f(n) = f(n-1)+f(n-2)+f(n-3)+f(4)+....+f(0)

public class Solution {
    public int JumpFloorII(int  n) {
        //递归
       //自底向上
        if(n <= 2 ){
            return n;
        }
        else{
            int sum = 1;
            while(n>0){
                n--;
                sum += JumpFloorII(n);
                
            }
            
            return sum;
            
        }
      
    }
     
}

相关文章

  • 剑指offer_6_1青蛙变态跳台阶

    青蛙变态跳台阶 方法一: 公式推导 f(n) = f(n-1)+f(n-2)+f(n-3)+f(4)+....+f...

  • 剑指Offer(九)

    剑指Offer(九) 变态跳台阶 题目描述 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该...

  • 《剑指offer》之Python青蛙变态跳台阶

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

  • [剑指offer] 变态跳台阶

    本文首发于我的个人博客:尾尾部落 题目描述 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该...

  • 变态跳台阶 剑指offer

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

  • 剑指offer 变态跳台阶

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

  • [剑指Offer]变态跳台阶

    本文首发于我的个人博客Suixin’s Blog原文: https://suixinblog.cn/2019/03...

  • 剑指offer

    剑指offer题目 1 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。...

  • leetcode--recursion(1)

    剑指 Offer 10- II. 青蛙跳台阶问题 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一...

  • 青蛙跳台阶问题

    《剑指offer》面试题10(题目二):青蛙跳台阶问题。 题目:一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。...

网友评论

      本文标题:剑指offer_6_1青蛙变态跳台阶

      本文链接:https://www.haomeiwen.com/subject/iyxezctx.html