LeetCode高频题70. 爬楼梯，青蛙跳台阶，暴力递归的尝试，改记忆化搜索和动态规划代码

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

基础知识：
（3）斐波那契数列：暴力递归改动态规划
（4）用矩阵乘幂的方法，求斐波那契数列f(n)=f(n-1)+f(n-2)，不用递归求，速度非常非常快
（5）类似斐波那契数列：奶牛生牛问题：奶牛生下来3年可以成熟生小牛，请问第N年一共多少牛
（6）人或者青蛙走台阶，每次它可以一步走1阶，或2阶，请问总共n层能有多少种走法
（7）一个N位字符串s，只包含0和1的，要求每个0左边都是1才达标，请问01组合出s有多少种组合方法
【8】一个2N的表格，砖块是12的尺寸，可以横着放或竖着放，请问2*N列表格有多少种放法？

---

文章目录

• LeetCode高频题70. 爬楼梯，青蛙跳台阶，暴力递归的尝试，改记忆化搜索和动态规划代码
• • @[TOC](文章目录)
• 题目
• 一、审题
• 关键在暴力递归的尝试
• 之所以设计算法题，就是希望你别太暴力，而是有优化算法的能力，咱们改记忆化搜索代码或者动态规划代码
• 总结

题目

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

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

---

一、审题

示例 1：

n=1
就一种：1

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

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

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

提示：

1 <= n <= 45

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

关键在暴力递归的尝试

不妨设f(n)是台阶有n阶，从1–n阶跳法有多少种？

你在n阶处
请问你是n-1那迈1阶来的？【那f(n-1)就是我们的跳法数量】
或者你是n-2那迈2阶来的？【那f(n-2)就是我们的跳法数量】

因为题目说了只能跳1阶，或者2阶
你从1—n不管咋跳，完整走完n阶算一种跳法

因此这就是一个简单的递归推理式子
f(n)=f(n-1)+f(n-2)

当然了，笔试我们用这个函数编写代码是无法通过的，速度太慢

咱们先完成这个代码：

        //f(n)=f(n-1)+f(n-2)
        //f=climbStairsReview
        public int climbStairsReview(int n) {
            if (n == 1) return 1;
            if (n == 2) return 2;

            return climbStairsReview(n - 1) + climbStairsReview(n - 2);
        }

测试结果：

    public static void test(){
        Solution solution = new Solution();
        System.out.println(solution.climbStairs(4));
        System.out.println(solution.climbStairsReview(4));
    }

    public static void main(String[] args) {
        test();
    }

5
5

之所以设计算法题，就是希望你别太暴力，而是有优化算法的能力，咱们改记忆化搜索代码或者动态规划代码

显然一个n一定对应一个结果
f有一个依赖方程
就是动态规划的转移方程呗

因此用dp[n]记录n阶时，你的跳法有多少种？
dp是一个1维长度是n+1的表格，n=0我们不用

因为f=fn-1+fn-2，所以根据这个方程，我们就知道dp[n]是dpn-1+dpn-2了
很简单

手撕代码：

        public int climbStairsReviewDP(int n) {
            if (n == 1) return 1;
            if (n == 2) return 2;
            int[] dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 2;

            for (int i = 3; i <= n; i++) {
                dp[i] = dp[i - 1] + dp[i - 2];//暴力递归改来的
            }

            return dp[n];//结果
        }

这就用空间dp
换的了时间
加速了算法

测试：

    public static void test(){
        Solution solution = new Solution();
        System.out.println(solution.climbStairs(4));
        System.out.println(solution.climbStairsReview(4));
        System.out.println(solution.climbStairsReviewDP(4));
    }

    public static void main(String[] args) {
        test();
    }

5
5
5

LeetCode测试：


算法考你就是想让你优化代码
就是这个意思

后来大量的公司，就改变这个题目为青蛙跳台阶问题，
换了名字，函数，代码没有变动

包括你说还能一步跳3阶呢？？？
那不就是f=fn-1+fn-2+fn-3
这不就是多了一种跳法？？不难的

类似的关于斐波那契数列的问题，多得很
我都说过：
（3）斐波那契数列：暴力递归改动态规划
（4）用矩阵乘幂的方法，求斐波那契数列f(n)=f(n-1)+f(n-2)，不用递归求，速度非常非常快
（5）类似斐波那契数列：奶牛生牛问题：奶牛生下来3年可以成熟生小牛，请问第N年一共多少牛
（6）人或者青蛙走台阶，每次它可以一步走1阶，或2阶，请问总共n层能有多少种走法
（7）一个N位字符串s，只包含0和1的，要求每个0左边都是1才达标，请问01组合出s有多少种组合方法
【8】一个2N的表格，砖块是12的尺寸，可以横着放或竖着放，请问2*N列表格有多少种放法？

---

总结

提示：重要经验：

1）斐波那契数列，和类似斐波那契数列，都是通过简单的递归函数，改为动态规划的
2）这题经常出现在各大厂笔试面试中，很简单很简单
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。