LeetCode-70. 爬楼梯(java)

bug菌

发布于 2023-05-27 15:22:12

2250

发布于 2023-05-27 15:22:12

文章被收录于专栏：《项目实战教学》

一、前言：

👨‍🎓作者：bug菌 ✏️博客：CSDN、掘金等 💌公众号：猿圈奇妙屋 🚫特别声明：原创不易，转载请附上原文出处链接和本文声明，谢谢配合。 🙏版权声明：文章里可能部分文字或者图片来源于互联网或者百度百科，如有侵权请联系bug菌处理。

二、题目描述：

题目： 假设你正在爬楼梯。需要 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

题目来源：LeetCode官网题目难度：⭐⭐

三、思路分析：

思路1：

首先遇到这种题目，第一感觉就是找规律推演，具体推演如下：

第1节台阶：1种(爬1级)
第2节台阶：2种(爬1级或爬2级)
第3节台阶：3种(1 级 + 1 级 + 1 级或1 级 + 2 级或2 级 + 1 级)
第4节台阶：5种
第4节台阶：8种
...
第n节台阶：从n-1级台阶爬1级或从n-2级台阶爬2级。

推演得到一个递推公式：f(n) = f(n-1) + f(n-2)

所以这里我们就可以用递归解决这个问题啦：但明显不是最优解啊，存在很多冗余计算。

思路2：

推演得到公式：dp[i] = dp[i-1] + dp[i-2] 你还可以使用动态规划来解题呀，具体思路如下：

初始化状态：i = 0 级开始爬的，所以从第 0 级爬到第 0 级，只有一种方案，即 dp[0]=1； i = 1 代表从第 0 级到第 1 级也只有一种方案，即爬一级，dp[0] = 1。
遍历顺序：由状态转移方程知道dp[i] = dp[i−1] + dp[i−2] ,所以从前往后遍历即可。
返回值：因为一共计算 n 阶楼梯有多少方案，所以返回dp[n]。

四、算法实现：

1、递归法_AC代码

具体算法代码实现如下：

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

2、动态规划_AC代码

具体算法代码实现如下：

class Solution {
         public int climbStairs(int n) {
  
             //先定义
             int p = 0, q = 0;
  
             //初始化=1;
             int r = 1;
  
             for (int i = 1; i <= n; i++) {
                 //赋值给f(n-2)
                 p = q;
                 //赋值给f(n-1)
                 q = r;
                 //求f(n)
                 r = p + q;
             }
             return r;
         }
     }