leetcode每日一练-第70题-爬楼梯

这篇具有很好参考价值的文章主要介绍了leetcode每日一练-第70题-爬楼梯。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

leetcode每日一练-第70题-爬楼梯,c++

 

一、思路

动态规划

二、解题方法

使用一个动态规划数组 dp 来记录到达每个台阶的不同方法数。初始情况下,当台阶数为 1 时,方法数为 1,当台阶数为 2 时,方法数为 2。然后,我们从第 3 阶开始逐步计算每一阶的方法数,方法数等于前一阶和前两阶方法数之和。最终,我们返回 dp[n],即到达 n 阶台阶的不同方法数。

三、code

class Solution {
public:
    int climbStairs(int n) {
        if(n<=2)
        {
            return n;
        }
        vector<int> dp(n+1,0);//使用一个动态规划数组 dp 来记录到达每个台阶的不同方法数
        //是一个用来存储动态规划状态的向量(数组),其中 n + 1 是数组的大小,初始化值都为 0。
        //在动态规划中,状态通常用一个数组(或向量)来表示,每个元素对应不同状态的解。在这个例子中,dp 数组的长度是 n + 1,表示有 n + 1 个不同的状态,索引从 0 到 n。
        dp[1]=1;
        dp[2]=2;
        //在动态规划的过程中,你会填充 dp 数组,其中 dp[i] 表示到达第 i 阶楼梯的不同方法数。最终,当你求解完整个数组后,你需要返回 dp[n],即到达楼顶的不同方法数。
        for(int i=3;i<=n;++i)
        {
            dp[i]=dp[i-1]+dp[i-2];//从第 3 阶开始逐步计算每一阶的方法数,方法数等于前一阶和前两阶方法数之和
        }
        return dp[n];//dp[n] 表示到达楼顶的不同方法数,其中 n 是楼梯的总阶数

    }
};

=========================================================================学到的知识:

① 

动态规划(Dynamic Programming,简称 DP)是一种解决问题的算法思想,通常用于求解具有重叠子问题和最优子结构性质的问题。它通过将问题分解为子问题并存储子问题的解,以避免重复计算,从而提高算法的效率。

动态规划常用于求解最优化问题,比如最短路径、最长公共子序列、背包问题等。它的核心思想是将原问题拆分为更小的子问题,然后通过解决子问题来解决原问题。在解决子问题时,动态规划会使用一种记忆化的方法,将子问题的解保存在数据结构中,以便后续直接获取,避免重复计算。

动态规划通常分为自顶向下和自底向上两种方式:

  1. 自顶向下:从大问题开始,逐步分解为子问题,然后通过递归或记忆化搜索来解决子问题。

  2. 自底向上:从小问题开始,逐步构建出更大的问题的解,通常采用迭代的方式,从子问题的解推导出原问题的解。

动态规划在算法设计和优化中具有广泛应用,能够有效地提高问题的求解效率,但也需要合理的状态定义、状态转移方程和边界条件来确保正确性。

vector<int> dp(n + 1, 0); 是一个用来存储动态规划状态的向量(数组),其中 n + 1 是数组的大小,初始化值都为 0

在动态规划中,状态通常用一个数组(或向量)来表示,每个元素对应不同状态的解。在这个例子中,dp 数组的长度是 n + 1,表示有 n + 1 个不同的状态,索引从 0n文章来源地址https://www.toymoban.com/news/detail-634856.html

到了这里,关于leetcode每日一练-第70题-爬楼梯的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • LeetCode:509. 斐波那契数 && 70. 爬楼梯 && 746. 使用最小花费爬楼梯

    斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n 1 给定 n ,请计算 F(n) 。 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬

    2024年02月05日
    浏览(48)
  • 算法leetcode|70. 爬楼梯(rust重拳出击)

    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 1 = n = 45 面对这道算法题目,二当家的再次陷入了沉思。 可以爬一阶或者两阶台阶,那也就是说,除了初始位置,和第一阶台阶,到达其他阶台阶 n 的方式

    2024年02月12日
    浏览(41)
  • LeetCode 70. 爬楼梯 C/C++/Python

    欢迎关注博主 Mindtechnist 或加入【Linux C/C++/Python社区】一起探讨和分享Linux C/C++/Python/Shell编程、机器人技术、机器学习、机器视觉、嵌入式AI相关领域的知识和技术。 专栏:LeetCode刷题 题目描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有

    2024年02月13日
    浏览(39)
  • leetcode 70.爬楼梯+209.长度最小的子数组

    70. 爬楼梯 - 力扣(LeetCode) 题目: 假设你正在爬楼梯。需要  n  阶你才能到达楼顶。 每次你可以爬  1  或  2  个台阶。你有多少种不同的方法可以爬到楼顶呢?  示例:   输入: n = 3 输出: 3 解释: 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 +

    2024年02月03日
    浏览(50)
  • Rust每日一练(Leetday0024) 爬楼梯、简化路径、编辑距离

    目录 70. 爬楼梯 Climbing Stairs  🌟 71. 简化路径 Simplify Path  🌟🌟 72. 编辑距离 Edit Distance  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 假设你正在爬楼梯。需要  n  阶你才能到达楼顶。

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

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

    2024年02月07日
    浏览(47)
  • 算法打卡day39|动态规划篇07| Leetcode 70. 爬楼梯(进阶版)、322. 零钱兑换、279.完全平方数

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

    2024年04月14日
    浏览(65)
  • leetcode每日一练-第53题-最大子数组和

    一、思路 动态规划 二、解题方法 使用了两个变量 maxSum 和 currentSum 来分别记录全局的最大和和当前连续子数组的和。遍历数组时,我们不断更新 currentSum ,并比较是否需要更新 maxSum 。最后, maxSum 就是最大的连续子数组和。 三、code ===================================================

    2024年02月10日
    浏览(36)
  • leetcode每日一练-第278题-第一个错误的版本

      一、思路 二分查找——因为它可以快速地将版本范围缩小一半,从而更快地找到第一个坏版本。 二、解题方法 维护一个左边界 left 和一个右边界 right ,在每一步循环中,我们计算中间版本 mid ,然后检查它是否是坏版本。如果是坏版本,说明第一个坏版本在 mid 或者它之

    2024年02月14日
    浏览(46)
  • leetcode每日一练-第98题- 验证二叉搜索树

        一、思路 因为要验证多个节点是否是二叉搜索树,因此使用 递归 二、解题方法 设计一个递归函数 helper(root, lower, upper) 来递归判断,函数表示考虑以 root 为根的子树,判断子树中所有节点的值是否都在 (l,r)的范围内(注意是开区间)。如果 root 节点的值 val 不在 (l,r)的范

    2024年02月15日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包