70.爬楼梯

ゝ一纸荒年。 2022-09-13 04:16 196阅读 0赞

题目描述：

假设你正在爬楼梯。需要 *n* 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例：

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

解题方法：简单一看，此题便是典型的斐波那契数列，即当 n >= 3 时，f(n) = f(n - 1) + f(n - 2)。那么，此题就有两种方法，迭代和递归。需要注意的是在 LeetCode 中使用递归的时候会超时。代码如下：

public class ClimbStairs {
    
        // 迭代
        public static int climbStairs(int n) {
            if (n <= 2) {
                return n;
            }
            int temp1 = 1;
            int temp2 = 2;
            for (int i = 3; i <= n; i++) {
                int result = temp1 + temp2;
                temp1 = temp2;
                temp2 = result;
            }
            return temp2;
        }
    
        // 递归
        public static int climbStairs2(int n) {
            if (n == 1 || n == 2) {
                return n;
            } else {
                return climbStairs2(n - 1) + climbStairs2(n - 2);
            }
        }
    
        public static void main(String[] args) {
            long startTime = System.currentTimeMillis();
            int result = climbStairs(6);
            System.out.println("result = " + result);
            long endTime = System.currentTimeMillis();
            System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
        }
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，196人围观）

还没有评论，来说两句吧...

相关阅读

相关 70：爬楼梯

昨天拿到题一样的思路，递推嘛 class Solution: def climbStairs(self, n: int) -> int: ...

港控/mmm°/ 2024年04月19日 09:56/ 0 赞/ 92 阅读

相关 70. 爬楼梯

70. 爬楼梯假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？示例 1： > 输入：n

妖狐艹你老母/ 2024年03月30日 15:10/ 0 赞/ 73 阅读

相关 70. 爬楼梯

70. 爬楼梯题干描述解题思路 1. 确定dp数组以及下标的含义 2. 确定递推公式 3. dp数组如何初始化

爱被打了一巴掌/ 2023年10月16日 15:52/ 0 赞/ 56 阅读

相关 70. 爬楼梯

//到达n阶只可能来自n-1和n-2,所以f(n)=f(n-1)+f(n-2) //1 2 3 5 8 13 int climbStairs(int n

川长思鸟来/ 2023年10月09日 10:32/ 0 赞/ 47 阅读

相关 70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：

男娘i/ 2023年10月04日 08:38/ 0 赞/ 29 阅读

相关 70. 爬楼梯

> 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 > > 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ > > 注意：给定 n 是一个正整数。

梦里梦外;/ 2022年10月08日 15:20/ 0 赞/ 185 阅读

相关 70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入

超、凢脫俗/ 2022年10月07日 07:49/ 0 赞/ 182 阅读

相关 70.爬楼梯

题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？示例：输入： 2 输出

ゝ一纸荒年。/ 2022年09月13日 04:16/ 0 赞/ 197 阅读

相关 LeetCode70.爬楼梯

假设你正在爬楼梯。需要 n 步你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1

雨点打透心脏的1/2处/ 2022年05月26日 06:46/ 0 赞/ 179 阅读

相关 70.爬楼梯

//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 // // 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ // // 注意：给定

古城微笑少年丶/ 2021年06月22日 15:38/ 0 赞/ 423 阅读