70. 爬楼梯--4种解法（递归，递归-记忆数组，迭代-数组，迭代-累加）LeetCode_爬楼迭代程序

题目

70. 爬楼梯

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

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

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

示例 1：

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

示例 2：

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

解法1：递归

/**
 * 思路：
 * 通过观察爬楼梯符合斐波那契数
 * 递归解决
 */
    public int climbStairs(int n) {
        if (n<=2){
            return n;
        }
        return climbStairs(n-1)+climbStairs(n-2);
    }
1
2
3
4
5
6
7
8
9
10
11

时间复杂度：O2^n

空间复杂度：O1

解法2：记忆数组

/**
 * 思路：
 * 通过观察爬楼梯符合斐波那契数
 * 递归解决
 * 加入记忆数组，如果值在记忆数组中存在直接返回
 */
    public static int climbStairs(int n) {
        if (n<=2){
            return n;
        }
        int[] arr_Memory=new int[n+1];
        return recursive(arr_Memory,n);
    }

    private static int recursive(int[] arr_memory, int n) {
        if (n<=2){
            return n;
        }
        if (arr_memory[n]!=0){
            return arr_memory[n];
        }
        arr_memory[n] = recursive(arr_memory, n - 1) + recursive(arr_memory, n - 2);
        return arr_memory[n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度：On

空间复杂度：On

解法3：迭代（累加）

/**
 * 思路：
 * 通过观察爬楼梯符合斐波那契数
 * 累加的求出第n层有多少策略
 */
    public int climbStairs(int n) {
        if (n<=2){
            return n;
        }
        int first=1,second=2;
        for (int i=3;i<=n;i++){
            int tmp=first+second;
            first=second;
            second=tmp;
        }
        return second;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度：On

空间复杂度：O1

解法4：迭代（数组）

/**
 * 思路：
 * 通过观察爬楼梯符合斐波那契数
 * 数组存放所有的fib数
 */
    public int climbStairs(int n) {
        if (n<=2){
            return n;
        }
        int[] arr=new int[n+1];
        arr[1]=1;arr[2]=2;
        for (int i=3;i<=n;i++){
            arr[i]=arr[i-1]+arr[i-2];
        }
        return arr[n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度：On

空间复杂度：On