每日一题：Leetocde-70 爬楼梯

力扣题目

解题思路

java代码

力扣题目：

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

解题思路：

解法思路：

• 首先，对于 n = 1 时，只有一种方法能到达，即直接一步到位，所以返回 1 。
• 对于 n = 2 时，有两种方法，一步一步走或者一步跨两级，所以返回 2 。
• 然后，使用动态规划的思想来解决。定义三个变量 a 、 b 和 c ，初始时 a = 1 表示到达第一级的方法数， b = 2 表示到达第二级的方法数。
• 通过一个循环从第三级开始计算，每一级的方法数 c 等于前两级的方法数之和（即 c = a + b ），然后更新 a 和 b 的值，为下一次计算做准备。

代码执行过程：
以 n = 3 为例，

• 初始时， a = 1 ， b = 2 。
• 第一次循环， i = 3 ， c = 1 + 2 = 3 ，然后 a = 2 ， b = 3 。
• 循环结束，返回 c ，即到达第三级的方法数为 3 。

这种方法的时间复杂度为 O(n) ，空间复杂度为 O(1) ，因为只使用了固定的几个变量来存储中间结果。

例如，如果 n = 4 ，计算过程如下：

• 初始： a = 1 ， b = 2 。
• 第一轮： c = 3 ， a = 2 ， b = 3 。
• 第二轮： c = 5 ，此时返回 c ，即到达第四级的方法数为 5 

java代码：

package org.example.mouth7.today23;

public class Leetcode70 {
    public static void main(String[] args) {
        System.out.println(climbStairs(3));
    }
    public static int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int a = 1;
        int b = 2;
        int c = 0;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

更多详细内容同步到公众号，感谢大家的支持！

每天都会给刷算法的小伙伴推送明日一题，并且没有任何收费项