剑指offer——变态跳台阶

做了一个算法题,还是蛮有趣的,不过每次做这种题都怀疑人生,为什么别人想得到,我却想不到?(好吧,承认智商不在线0_O)

问题:

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

解法一:

先列举一下台阶数,找找规律。

f(1) = 1     //1个台阶,总跳法只有1种

f(2) = f(2 – 1) + f(2 – 2)  //2个台阶,2-1表示跳一次1阶的跳法

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

f(n) = f(n-1) + f(n-2) + … + f(n-(n – 2)) + f(n-(n-1)) + f(n-n)

说明: 

1)这里的f(n) 代表的是n个台阶有一次1,2,3 … 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(n) = f(0) + f(1) + f(2) + f(3) + … + f(n-1)

其中f(0)表示一次跳n阶的跳法,n个阶梯,一次跳n阶,那么跳法只有一种,所以我们将f(0)置1。

public class Solution{
        public int JumpFloorII(int target) {
		int[] array = new int[1000];
		if(target <= 0) {
			return 0;
		}
		array[0] = 1;
		array[1] = 1;
		for(int i = 2; i <= target; i++) {
			array[i] = 0;
			for(int j = 0; j < i; j++) {
				array[i] += array[j];
			}
		}
		return array[target];
	}
}

时间复杂度:O(n^2)

有没有办法再降低?那就再找找规律

解法二:

解法一推出:

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

那么:

f(n-1) = f(0) + f(1) + f(2) + … + f(n-2)

得到:

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

也就是说跳n阶台阶的跳法是跳n-1阶台阶跳法的2倍,又由f(1) = 1,那么

f(2) = 2 * f(1) = 2 = 2^1

f(3) = 2 * f(2) = 4 = 2^2

f(4) = 2 * f(3) = 8 = 2^3

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

所以

public class Solution{
        public int JumpFloorII(int target) {
		int i = 1;
		return i<<(target - 1);   //<<为移位运算符,左移一位,则扩大2倍
	}
}

 

这就是最简单的方法了,不过我想不通,怎么还会有人用递归这种如此耗时的方法。。。

文章已创建 65

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部