「力扣」70. 爬楼梯

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 45

题解

其实这种场景题，最基本的难点就是如何找规律，只有找到规律才能有可能把代码写出来。

对n从1开始进行分析。

n = 1: 
1. 1阶

n = 2: 
1. 1阶 + 1阶
2. 2阶

n = 3:
1. 1阶 + 1阶 + 1阶
2. 1阶 + 2阶
3. 2阶 + 1阶

n = 4:
1. 1阶 + 1阶 + 1阶 + 1阶
2. 1阶 + 1阶 + 2阶
3. 1阶 + 2阶 + 1阶
4. 2阶 + 1阶 + 1阶
5. 2阶 + 2阶

通过上面我们得到如下结论：

f(1) = 1;
f(2) = 2;
f(3) = 3;
f(4) = 5;

变换下：

f(1) = 1;
f(2) = 2;
f(3) = f(2) + f(1) = 3;
f(4) = f(3) + f(2) = 5;

所以：

f(1) = 1;
f(2) = 2;
f(n) = f(n - 1) + f(n - 2)

递归

有了上面的公式我们可以通过递归来实现。

class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

提交到力扣：

提示当n = 45的时候超时了。

本地测试下：

通过本地测试可知，耗时3秒多。

递归耗时主要是因为有重复计算，通过n = 5来看下哪些是重新计算的。

图中相同颜色部分都是重复计算了，f(2)和f(1)虽然没有做算数运算，但是程序是开辟了栈空间的。

怎么解决呢？可以通过记忆法将已经计算过的存储起来，比如可以使用数组来存储。

class Solution {
    public int climbStairs(int n) {
        int[] memory = new int[n + 1];
        memory[0] = 1;
        memory[1] = 2;
        return climbStairs(n, memory);
    }

    private int climbStairs(int n, int[] memory) {
        if (memory[n - 1] > 0) {
            return memory[n - 1];
        }
        memory[n - 1] = climbStairs(n - 1, memory) + climbStairs(n - 2, memory);
        return memory[n - 1];
    }
}

提交到力扣：

上面的代码有很多 memory[n - 1]，这是因为n的最小值是1，这里可以简化下，允许n = 0，那么f(0) = 1, f(1) = 1。

class Solution {
    public int climbStairs(int n) {
        int[] memory = new int[n + 1];
        memory[0] = 1;
        memory[1] = 1;
        return climbStairs(n, memory);
    }

    private int climbStairs(int n, int[] memory) {
        if (memory[n] > 0) {
            return memory[n];
        }
        memory[n] = climbStairs(n - 1, memory) + climbStairs(n - 2, memory);
        return memory[n];
    }
}

动态规划

上面使用的记忆法能够解决问题，但是还有优化的空间。上面的记忆数组会将n个数组都记录其中，但是其实程序每次计算的时候只关心前两个值，所以我们可以使用动态规划的思想，每次将计算结果动态保存起来即可。

class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        
        int p = 1;
        int q = 2;
        int r = 0;
        for (int i = 3; i <= n; i++) {
            r = p + q;
            p = q;
            q = r;
        }
        return r;
    }
}

p和q分别代表climbStairs(n-2)和climbStairs(n-1)的值，这两个值是动态变化的，因为每次计算climbStairs(n)的时候只关心climbStairs(n-2)和climbStairs(n-1)的值，那么每次计算后，就将climbStairs(n-2)的值赋值给climbStairs(n-1)，将当前计算结果赋值给climbStairs(n-1)。

下图简单介绍下，索引i由3变为4的过程。

上面的代码中总共遍历了n - 2次，因为前面通过对n = 1和n = 2的情况进行了判断，其实可以不要这两个判断，一次性循环n次。

import java.util.Arrays;

class Solution {
    public int climbStairs(int n) {
        int p = 0;
        int q = 1;
        int r = 1;
        for (int i = 1; i <= n; i++) {
            r = p + q;
            p = q;
            q = r;
        }
        return r;
    }
}