跳台阶

题目描述

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

方法一

首先就是最笨的方法。

  1. n个台阶全部跳1级台阶,有1种跳法。

  2. n个台阶有一个跳2级台阶,有Cn11C_{n-1}^1种跳法。

  3. n个台阶有一个跳3级台阶,有Cn22C_{n-2}^2种跳法。

  4. n个台阶有一个跳n/2级台阶,有Cn(n/21)n/21C_{n-(n/2-1)}^{n/2-1}种跳法。

最后相加即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int JumpFloor(int target) {
if (target <= 0) {
return 0;
}

int i = 0;
int n = 0;
while (i <= target / 2) {
if (i == 0) {
n += 1;
} else {
n += factorial(target - i, i);
}
i++;
}
return n;
}

/**
* 计算阶乘
*/
public int factorial(int a, int b) {
long aa = 1, bb = 1;
for (int i = 0; i < b; i++) {
aa *= (a - i);
bb *= (b - i);
}
return (int) (aa / bb);
}

方法二

其次可以采用找规律的方法。

f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5, 可以总结出f(n) = f(n-1) + f(n-2)的规律,但是为什么会出现这样的规律呢?假设现在6个台阶,我们可以从第5跳一步到6,这样的话有多少种方案跳到5就有多少种方案跳到6,另外我们也可以从4跳两步跳到6,跳到4有多少种方案的话,就有多少种方案跳到6,其他的不能从3跳到6什么的啦,所以最后就是f(6) = f(5) + f(4);这样子也很好理解变态跳台阶的问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int JumpFloor(int target) {
if (target <= 0) {
return 0;
}

if (target == 1) {
return 1;
}

if (target == 2) {
return 2;
}

int first = 1;
int second = 2;
int third = 0;

for (int i = 3; i <= target; i++) {
third = first + second;
first = second;
second = third;
}

return third;
}

方法三

最后一种方法,可以使用递归来解决。

对于n阶台阶来说,若最后一步跳了一个台阶,则有f(n - 1)种跳法;若最后一步跳了两个台阶,则有f(n-2)种跳法。则有斐波拉起序列

f(n)={1if n=12if n=2f(n1)+f(n2)if n>=3f(n) = \begin{cases} 1 &\text{if } n = 1 \\ 2 &\text{if } n = 2 \\ f(n-1) + f(n-2) &\text{if } n >=3 \end{cases}

1
2
3
4
5
6
7
8
9
10
11
12
13
public int JumpFloor(int target) {
if (target <= 0) {
return 0;
}

if (target == 1) {
return 1;
} else if (target == 2) {
return 2;
} else {
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
}
-------------本文结束感谢您的阅读-------------

本文标题:跳台阶

文章作者:huihui

发布时间:2018年10月21日 - 00:10

最后更新:2019年02月14日 - 19:02

原始链接:http://101.200.47.120:8011/2018/10/21/跳台阶/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。