【LeetCode热题100】【动态规划】爬楼梯

这篇具有很好参考价值的文章主要介绍了【LeetCode热题100】【动态规划】爬楼梯。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接:70. 爬楼梯 - 力扣(LeetCode)

就是个斐波那契数列,达到第三个台阶的跳法可以从第一个台阶直接跳两步或者是从第二个台阶跳一步,因此对于第n个台阶来说,可以从第n-2个台阶跳两步到达,也可以从第n-1个台阶到达,因此跳到第n个台阶的跳法等于前两个台阶的跳法之和

递归会超时

    int climbStairs(int n) {
        if(n==1||n==2)
            return n;
        return climbStairs(n-1)+ climbStairs(n-2);
    }

改迭代文章来源地址https://www.toymoban.com/news/detail-847739.html

class Solution {
public:
    int climbStairs(int n) {
        int a = 0, b = 0, c = 1;
        while (n--) {
            a = b;
            b = c;
            c = a + b;
        }
        return c;
    }
};

到了这里,关于【LeetCode热题100】【动态规划】爬楼梯的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode使用最小花费爬楼梯(动态规划)

    链接: 使用最小花费爬楼梯 题目描述 算法流程(方法一) 编程代码 优化代码 算法流程(方法二) 编程代码 代码优化

    2024年02月15日
    浏览(32)
  • 动态规划之使用最小花费爬楼梯【LeetCode】

    LCR 088. 使用最小花费爬楼梯 状态表示 ( 这是最重要的 ):dp[i]表示以第i级台阶为楼层顶部,到达第i层台阶的最低花费。 状态转移方程 ( 最难的 ): dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]); 初始化 :根据题意,我们需要知道到达第1层和第2层台阶的最低花费,第1层和第2层

    2024年03月16日
    浏览(42)
  • leetcode 动态规划(爬楼梯、零钱兑换、完全平方数)

    卡码网:57. 爬楼梯(opens new window) 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,表

    2024年01月17日
    浏览(42)
  • 【LeetCode 热题 100】矩阵 专题(大多原地算法,需要一定思维)

    解题思路 在 代码注释中!

    2024年02月15日
    浏览(51)
  • LeetCode刷题笔记【29】:动态规划专题-1(斐波那契数、爬楼梯、使用最小花费爬楼梯)

    动态规划(DP,Dynamic Programming)。 其解题思路对比 贪心算法的“直接选局部最优然后推导出全局最优” ;倾向于“ 由之前的结果推导得到后续的结果 ”。 很多时候二者具有相似性,不必死扣概念。 动态规划题目的核心是dp数组的概念和构建(递推公式); 所以具体的解题步骤

    2024年02月09日
    浏览(40)
  • LeetCode 0746. 使用最小花费爬楼梯:动态规划(原地)——不用什么从递归到递推

    力扣题目链接:https://leetcode.cn/problems/min-cost-climbing-stairs/ 给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼

    2024年02月03日
    浏览(41)
  • 【LeetCode题目详解】第九章 动态规划part01 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯 (day38补)

    斐波那契数  (通常用  F(n) 表示)形成的序列称为 斐波那契数列 。该数列由  0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: 给定  n ,请计算 F(n) 。 示例 1: 示例 2: 示例 3: 提示: 0 = n = 30 斐波那契数列大家应该非常熟悉不过了,非常适合作为动规第

    2024年02月07日
    浏览(47)
  • 【Leetcode】top 100 多维动态规划

    62 不同路径 一个机器人位于一个  m x n   网格的左上角,机器人每次只能向下或者向右移动一步,机器人试图达到网格的右下角,问总共有多少条不同的路径? 分析:dp[i][j] 代表走到 (i, j) 的路径总和数 递推规律:dp[i][j] = dp[i-1][j] + dp[i][j-1] 初始条件:dp[0][:] = 1 dp[:][0] = 1

    2024年03月26日
    浏览(47)
  • 螺旋矩阵 LeetCode热题100

    给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 模拟,朝一个方向走,走过的点标记一下,直到碰到边界或碰到已经走过的路,换个方向。右-下,下-左,左-上,上-右。直到走完所有点。

    2024年02月14日
    浏览(64)
  • LeetCode热题100——图论

    给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 输入:grid = [ [“1”,“1”,“1”,“1”,“0”], [“1”,“1”,“0”,“1”,“0”], [“1”,“1”

    2024年01月16日
    浏览(76)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包