爬楼梯和爬楼梯进阶c++

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

该题是动态规划入门题,可扩展性较强。主要思想参考代码随想录


题目分析

题目描述

  1. 基础爬楼梯,每次以1或2步爬楼梯,共n阶,求共有多少种爬楼梯方式
  2. 基础爬楼梯空间优化
  3. 每次爬楼梯有成本限制,如何以最小成本爬楼梯
  4. 每次爬楼梯可用步数与台阶阶数一致,如1阶可1步,2阶可1步或2步,…, n阶可1到n步前进,求爬楼梯方法数

题目分析

  1. 基础爬楼梯

    每次可用1步或两步进行爬楼梯,那么每次爬楼梯的方法可往前退一步或退两步,当知道前一步或前两步的方法数时,此时的方法数就可由前一步和前两步的方法数来确定。

    (1) dp数组:dp[i],代表爬i阶的方法数总数,

    (2) 递推公式:dp[i] = dp[i - 1] + dp[i - 2];

    (3) dp数组初始化:由递推公式可知,最少要初始化前两个dp数组的值,这里dp[0]的初始化存在争议,理论为0,但是为了计算dp数组,需要将其置为1,然后从i = 2开始遍历;这里可从i= 3开始遍历,越过dp[0]的初始化,dp[1] = 1; dp[2] = 2;(1 阶 + 1 阶, 2 阶),即根据遍历开始顺序初始化dp数组。

    (4) 遍历顺序:由递推公式可知,要从前往后依次遍历。

    (5) 打印dp数组,验证是否正确,c++中三种循环遍历方式

  2. 基础爬楼梯空间优化
    这里dp数组每次只使用前两个值,可建立一个大小为2的dp数组,然后每次循环的时候更新前两个数组的值即可,此时空间复杂度为常数:O(1);

  3. 带成本爬楼梯
    数组的每个下标作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。每当你爬上一个阶梯你都要花费对应的体力值,一旦支付了相应的体力值,你就可以选择向上爬一个或两个。

    (1) dp数组:dp[i],代表爬i阶花费的最小体力值,

    (2) 递推公式:由基础爬楼梯可知,爬楼梯的方法由前两个台阶方法确定,同理,最小花费也有前两个的花费确定,但是最后要加上本级台阶的花费,故dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

    (3) 初始化方式:这里最好从0开始,因为cost是从0开始,否则需要仔细思考两者的对应关系,

    (4) 同上
    (5) 同上

这里也可以对空间进行优化,优化方式如上

  1. 爬楼梯阶数递增
    此时每次i阶楼梯,可用1 2 3……i步去爬。则此时i阶的方法数,取决于前1-i阶的方法数,此时题目的类型也可以理解为一个完全背包问题,每阶台阶理解成一个完全背包问题,拿1-i范围内的数将这个背包填满,其中1-i个数每次可以无限取,问有多少种爬楼梯方式,便是问有多少种将背包填满的方式,关于背包问题,后序会有专门介绍,这里不过多展开

    (1) dp数组:dp[i] 代表爬i阶台阶的方法数

    (2) 递推公式:此时i阶的方法数,取决于前1-i阶的方法数,则dp[i] += dp[i - j], j = 1 2…i

    (3) 初始化方法:同上
    (4) 遍历顺序:同上
    (5)验证:同上

实践步骤

动态规划解题步骤:

  1. 确定dp数组的含义
  2. 确定递推公式
  3. dp数组初始化
  4. 确定遍历顺序
  5. 举例验证dp数组

代码实现

#include <iostream>
#include <vector>
using namespace std;

//基础爬楼梯
int climbStairs(const int& n) {
    //递归方式
    vector<int>dp(n + 1, 0);    //dp数组,代表当前台阶爬楼梯方法数
    dp[0] = 1;
    dp[1] = 1;  //另一种初始化方法,即初始化dp[1]和dp[2],从3开始遍历
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

//基础爬楼梯空间优化
int climbStairsplus(const int& n) {
    int res = 0;
    //递归方式
    vector<int>dp(2, 0);    //dp数组,代表当前台阶爬楼梯方法数
    dp[0] = 1;    //before2
    dp[1] = 1;  //before1//每次记录该该台阶的前两阶即可,但需实时更新前两节台阶数
    for (int i = 2; i <= n; i++) {
        res = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = res;
        
    }

    return res;
}

//带体力成本爬楼梯
int minCostClimbingStairs(vector<int>& cost) {
    vector<int> dp(cost.size());
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (int i = 2; i < cost.size(); i++) {
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    // 注意最后一步可以理解为不用花费,所以取倒数第一步,第二步的最少值
    return min(dp[cost.size() - 1], dp[cost.size() - 2]);
}

//带体力空间优化
int minCostClimbingStairsplus(vector<int>& cost) {
    int dp0 = cost[0];
    int dp1 = cost[1];
    for (int i = 2; i < cost.size(); i++) {
        int dpi = min(dp0, dp1) + cost[i];
        dp0 = dp1; // 记录一下前两位
        dp1 = dpi;
    }
    return min(dp0, dp1);
}

//每次爬楼梯方式与楼梯阶数一致
int nclimbStairs(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) { // 遍历背包
        for (int j = 1; j <= i; j++) { // 遍历物品
            dp[i] += dp[i - j];
        }
    }
    return dp[n];
}

int main() {
    int n;  //共n阶台阶
    cin >> n;
    vector<int> cost(n);
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    //int res = climbStairs(n);
    int res = minCostClimbingStairs(cost);
    //int res = nclimbStairs(n);
   
    cout << "爬n阶台阶方法数或体力花费最小数:" << res << endl;
    system("pause");
    return 0;
}


总结:

复杂度

时间复杂度:for循环层数,一层:, O(n),两层:O(n^2),

空间复杂度:未优化:O(n),优化后O(1);

知识考察

该题是动态规划入门题,用来熟悉动态规划方法解题流程,后序n阶台阶n种步数牵扯到动态规划经典题:完全背包问题,后续将详细介绍背包问题,文章来源地址https://www.toymoban.com/news/detail-403543.html

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

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

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

相关文章

  • 动态规划入门篇——斐波那契数列与爬楼梯问题

           动态规划(Dynamic Programming,简称DP)是运筹学的一个分支,也是求解多阶段决策过程最优化问题的一种方法。它主要用来解决一类最优化问题,通过将复杂问题分解成若干个子问题,并综合子问题的最优解来得到原问题的最优解。动态规划的核心在于对问题的状态进

    2024年03月14日
    浏览(42)
  • 爬楼梯【动态规划】

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

    2024年02月10日
    浏览(40)
  • 动态规划篇-01:爬楼梯

    本文为力扣70:爬楼梯的详细解析。 虽然这道题的标签是“简单”,但是只有简单的题才能让我们专注于这类题的解题框架上。 一般来说动态规划会有三种解法:暴力解法、使用了备忘录自上而下的递归解法、使用了数组的自下而上的迭代解法。接下来我会对这三种解法逐一

    2024年01月17日
    浏览(31)
  • 最小花费爬楼梯(动态规划)

    题目: 给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。 输入格式: n 个整数,代表从

    2024年02月07日
    浏览(37)
  • 【LeetCode热题100】【动态规划】爬楼梯

    题目链接:70. 爬楼梯 - 力扣(LeetCode) 就是个斐波那契数列,达到第三个台阶的跳法可以从第一个台阶直接跳两步或者是从第二个台阶跳一步,因此对于第n个台阶来说,可以从第n-2个台阶跳两步到达,也可以从第n-1个台阶到达,因此跳到第n个台阶的跳法等于前两个台阶的跳

    2024年04月11日
    浏览(105)
  • 动态规划之使用最小花费爬楼梯

    题目链接选自力扣 : 使用最小花费爬楼梯 先根据示例 1 来理解一下题目的意思. 可以看到, 此时一共有两个起始位置 0 ,1. 并且这三个位置都对应了一定的费用 10, 15 当我们选择从某个地方开始想要向上走就得支付当前位置的费用才可以向上一格或者两格. 当前这个示例就是从

    2024年02月10日
    浏览(63)
  • day38|动态规划-爬楼梯问题

    动态规划比较重要的是找到前后两个状态之间的联系,在向后遍历的过程中注意遍历的顺序和初始化操作。 动归基础类问题 背包问题 打家劫舍 股票问题 子序列问题 动态规划类的问题代码都是比较简洁的,按照dp打印逻辑观察打印出来的数值。 dp数组以及下标的含义dp[i][j

    2024年02月07日
    浏览(40)
  • 动态规划之 70爬楼梯(第2道)

    题目: 假设你正在爬楼梯。需要  n  阶你才能到达楼顶。 每次你可以爬  1  或  2  个台阶。你有多少种不同的方法可以爬到楼顶呢? 题目链接:70. 爬楼梯 - 力扣(LeetCode) 示例: 解法:  假如爬到第 i 层,那要么是从第 i-1 层爬上来的,要么是从第 i-2 爬上来的。

    2024年02月13日
    浏览(59)
  • LeetCode使用最小花费爬楼梯(动态规划)

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

    2024年02月15日
    浏览(31)
  • DAY42:动态规划(二)斐波那契数列+爬楼梯+最小花费爬楼梯

    斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: 给定 n ,请计算 F(n) 。 示例 1: 示例 2: 示例 3: 提示: 0 = n = 30 思路:动规五步 确定dp数组和数组下标含义 DP题目都需要定义一维

    2024年02月13日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包