动态规划之爬楼梯

迷南。 2023-09-30 21:14 10阅读 0赞

[70. 爬楼梯][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

爬楼梯实质上也可以看作一个斐波拉契数列：

class Solution:
        def climbStairs(self, n: int) -> int:
            dp = [0] * (n+1)
            dp[0] = 1
            dp[1] = 1
            for i in range(2, n+1):
                dp[i] = dp[i-1] + dp[i-2]
    
            return dp[n]

类似题目 [剑指 Offer 10- II. 青蛙跳台阶问题][Offer 10- II.]：

class Solution:
        def numWays(self, n: int) -> int:
            if n == 0 or n == 1:
                return 1
    
            dp = [0] * (n + 1) 
            dp[0] = 1   # 0 个台阶有 1 种 方法
            dp[1] = 1   # 1 个台阶有 1 种方法
        
    
            for i in range(2, n + 1):
                dp[i] = dp[i - 1] + dp[i - 2]
    
            return dp[n] % 1000000007

[70.]: https://leetcode.cn/problems/climbing-stairs/
[Offer 10- II.]: https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

发表评论取消回复

表情：

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

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

相关阅读

相关 Java之动态规划之爬楼梯问题

目录 0.动态规划问题一.爬楼梯 1.题目描述 2.问题分析 3.代码实现二.使用最小花费爬楼梯 1.题目描述 2.问题分析 3.代码实现三. 爬楼梯

曾经终败给现在/ 2024年03月27日 13:39/ 0 赞/ 90 阅读

相关动态规划之使用最小花费爬楼梯

1. 题目分析题目链接选自力扣 : [使用最小花费爬楼梯][Link 1] ![image.png][] 先根据示例 1 来理解一下题目的意思. ![ima

「爱情、让人受尽委屈。」/ 2024年03月16日 22:01/ 0 赞/ 56 阅读

相关动态规划之爬楼梯

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

迷南。/ 2023年09月30日 21:14/ 0 赞/ 11 阅读

相关动态规划之Climbing Stairs(爬楼梯) java实现

问题有一个楼梯，总共有n阶台阶。每一次，可以上一个台阶，也可以上两个台阶。问，爬这样的一个楼梯，一共有多少不同的方法？如n=3，可以爬上这个梯子的方法有：\[1,

小鱼儿/ 2022年12月30日 08:00/ 0 赞/ 142 阅读

相关利用动态规划求解爬楼梯问题

题目描述：假设你正在爬楼梯，需要n阶才能到达楼顶。每次可以爬1或2阶，你有多少种不同的方法可以爬到楼顶呢？其中n是一个正整数。思路和算法：利用动态规划，用f

约定不等于承诺〃/ 2022年12月28日 05:30/ 0 赞/ 171 阅读

相关算法题目——爬楼梯(动态规划)

题目链接：[70.爬楼梯][70.] 类似题目：[1646.获取生成数组中最大值][1646.] ![在这里插入图片描述][watermark_type_ZHJvaWRz

╰+哭是因爲堅強的太久メ/ 2022年09月14日 11:14/ 0 赞/ 212 阅读

相关动态规划--爬楼梯

1、题目： You are climbing a stair case. It takes n steps to reach to the top. Each time y

心已赠人/ 2022年05月23日 07:47/ 0 赞/ 214 阅读

相关动态规划--最小代价爬楼梯

1、题目： On a staircase, the `i`\-th step has some non-negative cost `cost[i]` assigned (0

Myth丶恋晨/ 2022年05月23日 07:46/ 0 赞/ 220 阅读

相关 [算法提高] 动态规划爬楼梯

\[问题背景\] 来源：LeetCode(力扣) 编号：[70. 爬楼梯][70.] 内容：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或

喜欢ヅ旅行/ 2022年03月06日 04:03/ 0 赞/ 242 阅读

相关 [动态规划] 70. 爬楼梯

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

约定不等于承诺〃/ 2021年12月09日 00:19/ 0 赞/ 269 阅读