设计与思考

改变世界的力量

0%

爬楼梯

发表于 分类于

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

1
2
3
4
5
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

1
2
3
4
5
6
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

思路

  1. 最简单的思路, 用递归的思想解决. 爬3层楼梯可以看成爬2层+1层问题的方法集合, 终止条件就是当n计算到1
  2. 因为存在大量重复计算, 所以可以用HashMap或者数组存储中间结果
  3. 当然也可以不用递归, 直接迭代计算

代码实现

1
2
3
4
5
6
7
8
9
public int climbStairs(int n) {
    if(n <= 1) {
        return 1;
    }
    if(n == 2) {
        return 2;
    }
    return climbStairs(n - 1) + climbStairs(n-2);
}

但是这种实现时间复杂度是O(n2), 有很多重复计算, 导致运行时间过长.
所以考虑缓存中间运算结果, 用HashMap或者数组都可以, 在这里用了数组来保存.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int climbStairs(int n) {
       int[] cache = new int[n + 1];
       return climbStairsWithCache(n, cache);
   }

   private int climbStairsWithCache(int n, int[] cache) {
       if (cache[n] != 0) {
           return cache[n];
       }
       if (n == 1) {
           cache[n] = 1;
           return 1;
       }
       if (n == 2) {
           cache[n] = 2;
           return 2;
       }
       int func2 = climbStairsWithCache(n - 2, cache);
       cache[n - 2] = func2;
       int func1 = climbStairsWithCache(n - 1, cache);
       cache[n - 1] = func1;
       return func2 + func1;
   }
1
2
3
4
5
6
7
8
9
public int climbStairs(int n) {
       int p = 0, q = 0, r = 1;
       for (int i = 1; i <= n; ++i) {
           p = q;
           q = r;
           r = p + q;
       }
       return r;
   }