首页 > 试题广场 >

跳台阶扩展问题

[编程题]跳台阶扩展问题
  • 热度指数:691450 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

数据范围:
进阶:空间复杂度 , 时间复杂度
示例1

输入

3

输出

4
示例2

输入

1

输出

1
推荐

关于本题,前提是n个台阶会有一次n阶的跳法。分析如下:

f(1) = 1

f(2) = f(2-1) + f(2-2)         //f(2-2) 表示2阶一次跳2阶的次数。

f(3) = f(3-1) + f(3-2) + f(3-3) 

...

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

 

说明: 

1)这里的f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。

2)n = 1时,只有1种跳法,f(1) = 1

3) n = 2时,会有两个跳得方式,一次1阶或者2阶,这回归到了问题(1) ,f(2) = f(2-1) + f(2-2) 

4) n = 3时,会有三种跳得方式,1阶、2阶、3阶,

    那么就是第一次跳出1阶后面剩下:f(3-1);第一次跳出2阶,剩下f(3-2);第一次3阶,那么剩下f(3-3)

    因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)

5) n = n时,会有n中跳的方式,1阶、2阶...n阶,得出结论:

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

    

6) 由以上已经是一种结论,但是为了简单,我们可以继续简化:

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

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

    可以得出:

    f(n) = 2*f(n-1)

    

7) 得出最终结论,在n阶台阶,一次有1、2、...n阶的跳的方式时,总得跳法为:

              | 1       ,(n=0 ) 

f(n) =     | 1       ,(n=1 )

              | 2*f(n-1),(n>=2)
public class Solution {
    public int jumpFloorII(int target) {
        if (target <= 0) {
            return -1;
        } else if (target == 1) {
            return 1;
        } else {
            return 2 * jumpFloorII(target - 1);
        }
    }
}

编辑于 2015-06-17 21:30:40 回复(217)
假设有n级的台阶,其实就是找组合数,将n分成n个0或者1(1,1,0,0,0,1)第一个必须是1,其中1表示未被前面步数包含,0表示被前面步数包含,比如如果是4步,(1,1,1,1)表示一次跳一步,(1,0,0,1)表示3,1(1,1,0,1)表示1,2,1所以组合应该为2的n-1次方
发表于 2015-10-10 13:20:41 回复(2)
//头像 //

每个台阶都有跳与不跳两种情况(除了最后一个台阶),最后一个台阶必须跳。所以共用2^(n-1)中情况

发表于 2015-06-03 22:36:45 回复(119)
public class Solution {
    public int jumpFloorII(int target) {
        if(target<=0)
            return 0;
        return 1<<(target-1);
    }
}

发表于 2016-04-18 14:03:46 回复(0)
class Solution {
public:
    int jumpFloorII(int number) {
/*        //第一种
        long int sum=0;
        if(number==0) return 1;
        else if(number==1) return 1;
        else if(number==2) return 2;
        else
        {
               for(int i=number-1; i>=0; i--)
                   sum += jumpFloorII(i);
        }
        
        return sum;
        */
        //第二种做法
        return pow(2, number-1);
    }
};
发表于 2015-10-09 16:36:30 回复(0)
class Solution {
public:
    int jumpFloorII(int number) {
			return pow(2,number-1);
    }
};

发表于 2016-11-18 20:08:04 回复(0)
因为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)
编辑于 2018-03-28 20:41:06 回复(46)
HXY头像 HXY
一行代码 return  1<<--number;
编辑于 2015-04-25 20:40:41 回复(125)
public class Solution {
    public int jumpFloorII(int target) {
        int sum=1;
        if(target==0||target==1||target==2)
            return target;
        for(int i=1;i<=target;i++){
            sum+=jumpFloorII(target-i);
        }
        return sum;
    }
}

发表于 2020-02-15 00:35:04 回复(0)
public class Solution {
    public int jumpFloorII(int target) {
        // 假设:f(n)表示:n个台阶第一次1,2,...n阶的跳法数;
        // 若第一次跳了1阶,则还剩n-1阶,
        // 假设:f(n-1)表示:n-1个台阶第一次1,2,...n-1阶的跳法数;
        // 若第一次跳了2阶,则还剩n-2阶,
        // 假设:f(n-2)表示:n-1个台阶第一次1,2,...n-2阶的跳法数;
        // ...
        // 把所以可能的情况(第一次可能跳1,2,...,n阶)加起来:
        // 可以求出:f(n) = f(n-1) + f(n-2) + ... + f(1)
        // 递归:f(n-1) = f(n-2) + ... + f(1)
        // 可以求出:f(n) = 2*f(n-1) 
        
        /*
        if (target <= 0) {
            return 0;
        } else if (target == 1) {
            return 1;
        } else {
            return 2 * jumpFloorII(target - 1);
        }
        */ 
        // 更实用的解法是:从下往上计算,避免了递归的多余计算量
        int a = 1, b = 0;
        if (target <= 0) {
            return 0;
        } else if (target == 1) {
            return 1;
        } else {
            for (int i = 2; i <= target; i++) {
                b = 2 * a;
                a = b;
            }
            return b;
        }
    }
}

编辑于 2017-03-14 01:31:46 回复(0)
可以看做是跳台阶问题的变种。
跳台阶,每次只能跳一个或两个台阶:
dp[i] = dp[i - 1] + dp[i - 2];
每次可以跳任意个:
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4] + ... + dp[1] + 1;
最后+1 表示一步跳到顶。
可以发现规律:
target     res
1            1
2            2
3            2 + 1 + 1 = 4
4            4 + 2 + 1 + 1 = 8
5            8 + 4 + 2 + 1 + 1 = 16
 所以直接返回2的(n - 1)次方就可以了。
public int jumpFloorII(int target) {
    return 1 << (target - 1);
}




发表于 2022-01-05 00:10:34 回复(0)
    /**
     * 解题思路:
     * 爬楼梯的变种,爬楼梯只能爬1阶或者2阶,所以需要x(n) = x(n-1)+x(n-2)
     * 那么能跑n阶,是不是意味着x(n) = x(n-1) + x(n-2) + x(n-3) + ... x(0)
     *
     * @author freedom wang
     * @date 2021-01-23 10:29:30
     */
    public int jumpFloorII(int target) {
        if (target == 0 || target == 1) {
            return 1;
        }

        int[] array = new int[target + 1];
        array[0] = 1;
        array[1] = 1;

        for (int i = 2; i < target + 1; i++) {
            int count = 0;
            for (int j = 0; j < i; j++) {
                count += array[j];
            }
            array[i] = count;
        }

        return array[target];
    }
发表于 2021-01-23 10:37:56 回复(0)

得出规律后,直接使用2的n-1次方公式。

public class Page79 {
    public int jumpFloorII(int target) {
        if (target == 0) {
            return 0;
        } else{
            return (int) Math.pow(2,target - 1);
        }
    }

    public static void main(String[] args) {
        Page79 page79 = new Page79();
        System.out.println(page79.jumpFloorII(3));
    }
}
发表于 2019-01-22 11:02:44 回复(0)
public class Solution {
    public int jumpFloorII(int target) {
        int sum = 1;
        while(target > 1){
            sum *= 2;
            target--;
        }
        return sum;
    }
}
或者是使用位运算
发表于 2018-08-03 11:55:29 回复(0)
class Solution {
public:
    int jumpFloorII(int number) {
        return 1<<(number-1);
    }
};
发表于 2017-10-20 22:57:26 回复(0)
当target等于1时,有1种跳法1<<--1
target=2时,有2种跳法1<<--2
target=3时,有4种跳法1<<--3
target=4时,有8中跳法1<<--4
.....
return 1<< -- target,所以这一句代码即可
发表于 2015-10-01 17:06:20 回复(0)
这不是一个编程逻辑题,其实就是一个数学归纳法罢了!最后可以推出这是一个首项是1,公比为2的等比数列!
public int jumpFloorPlus(int target) {
    if(target == 0)
      return 0;
    if(target == 1)
      return 1;
    return 2*jumpFloorPlus(target-1);
  }


发表于 2017-12-27 21:22:46 回复(0)
这道题如果用递归去解的话,可能时间会超时,感觉每次用递归解都很容易造成大量的冗余数据。所以个人觉得用动态规划比较好。
首先分析题干无非就是找规律。f(n)=f(n-1)+...f(0)
用个长度为target的数组,利用上边的规律,a[target-1]项即为题目答案。
public int jumpFloorII(int target) {
		if (target == 1)
			return 1;
		if (target == 2)
			return 2;
		int a[] = new int[target];
		a[0] = 1;
		a[1] = 2;
		for (int i = 2; i < target; i++) {
			int sum = 0;
			for (int j = 0; j < i; j++) {
				sum += a[j];
			}
			a[i] = sum + 1;
		}
		return a[target - 1];

}
发表于 2016-05-27 23:06:55 回复(1)
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number<=0:
            return 0
        else:
            return 2**(number-1)
Python:若有n个台阶,则 跳法为第一下跳1阶剩余台阶的 跳法为f(n-1),以及第一下跳2节剩余台阶跳法为f(n-2),以及第一下跳3阶剩余台阶 跳法为f(n-3),依次类推知道最后一次是一下子全部跳上去,方法为1,因此f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(1)+1,f(1)=1,f(2)=2..f(n)-f(n-1)=f(n-1)因此f(n)=2f(n-1)是等比数列,首项为1,比例 为2,f(n)=2^(n-1)
发表于 2017-10-18 15:25:49 回复(0)
结题思路:
1.如果是n不好说。我举个列子,n=4。
这里是直接跳到4的方案:
            第一种 青蛙直接跳到4
这里是直接跳到3,然后跳到4的方案:
            第二种 青蛙跳到3->4
这里是直接跳到2,然后跳到4的方案:
            第三种 青蛙跳到2->(4) #我这里为什么括号,是因为这个4,就是第一种青蛙跳的
            第四种 青蛙跳到2->(3->4)#理由同上
可以推出:
直接跳到1,然后跳到4的方案是:
            1->4
            1->(3->4)
            1->(2->(4))
            1->(2->(3->4))
可以找出一个规律。
代码如下:
public int jumpFloorII(int target) {
        if(target==1||target==2)
            return target;
        int i=target;
        int sum=2;
        while(target>2){
            sum=(int) (sum+Math.pow(2, target-2));
            target--;
        }
        return sum;
    }

发表于 2017-10-17 20:17:05 回复(0)
//1级有1种,2级有2种,3级有4种,之后每多一级台阶都有之前的两种走法,n级有2的n-1种跳法
class Solution {
public:
    int jumpFloorII(int number) {
	    int NumberOfSteps=2;
        if(number<=0)
            return -1;
        if(number==1||number==2)
            return number;
        for (int i=3;i<=number;i++){
            NumberOfSteps *= 2;
            
        }
        return NumberOfSteps;
    }
};

发表于 2016-03-18 01:02:22 回复(0)