爬楼梯

题意

假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?

样例

  • n=1 方法只有一种就是1
  • n=2 1+1 或者 2 两种方法
  • n=3 1+1+1 或者 1+2 或者 2+1 三种方法
  • …..

思路

逆向思维,例如 n = 4 ,那么他走的最后一步就只能是 1步 或者 2步
如果最后走的是1级台阶,那么之前走的就是3级台阶, 如果之前走的是2级台阶,那么之前走的就是2级台阶,
于是得到4阶台阶的走法就是3阶台阶的走法加上2阶台阶的走法。也就是3 + 2 = 5种。
如果还不明白的话 我这样看:

  • n=1:
  • n=2: 1+1 2
  • n=3: 1+1+1 1+2 2+1
  • n=4: 1+1+1+1 1+2+1 2+1+1 1+1+2 2+2

在原来的 n=3 的基础上,所有方法都加1步,变成了 1+1+1+1 1+2+1 2+1+1
然后再在 n=2 的基础上,所有方法都加2步,变成了 1+1+2 2+2
然后在看看 n=2n=3 的时候,分别加上2步和1步 就变成了 n=4 的所有方法

代码实现:递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
/**
* @param n: An integer
* @return: An integer
*/
public int climbStairs(int n) {
if (n == 1 || n == 2)
return n;

int now = climbStairs(n-2) + climbStairs(n-1);
return now;

}
}

递归方式虽然能实现这种,但是当n越大,程序运行时间就越长,最后还会导致栈溢出的情况,所以对算法进行了改进。

代码实现: 循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
/**
* @param n: An integer
* @return: An integer
*/
public int climbStairs(int n) {
if (n == 0) { //这里判断n == 0 是因为题目测试程序给的测试数据中有n = 0 时期望答案为1的设定。
return 1;
}
if (n == 1 || n == 2)
return n;
int[] array = new int[n + 1];
array[1] = 1;
array[2] = 2;
for (int i = 3; i <= n; i++)
array[i] = array[i - 1] + array[i - 2];
return array[n];
}
}

这样就不会出现栈溢出的情况了,但是可以看到使用数组还是占用了一定的空间,不够简洁,于是再次改进。

代码实现: 循环优化版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
/**
* @param n: An integer
* @return: An integer
*/
public int climbStairs(int n) {
if (n == 0) {//这里判断n == 0 是因为题目测试程序给的测试数据中有n = 0 时期望答案为1的设定。
return 1;
}
if (n == 1 || n == 2)
return n;
int f1 = 1;
int f2 = 2;
int fn = 0;
for (int i = 3; i <= n; i++) {
fn = f1 + f2;
f1 = f2;
f2 = fn;
}
return fn;
}
}

此方法就是每次将 f1f2 向后移动一次,以记录数据。避免浪费资源. 如下:

1
2
3
4
5
6
7
8
1,  2, 3, 5, 8, 13 ......
f1, f2, fn,

1, 2, 3, 5, 8, 13 ......
f1, f2, fn

1, 2, 3, 5, 8, 13 ......
f1, f2, fn

原题地址:

LintCode:爬楼梯

坚持原创技术分享,您的支持将鼓励我继续创作!