算法力扣刷题记录 七十【70. 爬楼梯及算法性能分析:时间复杂度和空间复杂度】

news/2024/9/25 17:20:05/

前言

动态规划章节第二篇。记录 七十【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

二、尝试实现

分析题目

  1. 拿到题目分析应该用什么方法:有递归(回溯)、贪心算法、动态规划。首先分析题目:刚拿到时,直给了两个示例,看不出来什么,那么就多写几个n,找找规律。
  • 当n=1时,1种方案:{1}
  • 当n=2时,2种方案:{1,1}和{2};
  • 当n=3时,3种方案:{1,1,1}和{1,2}和{2,1}
  • 当n=4时,5种方案:{1,1,1,1}和{1,1,2}和{1,2,1}和{2,1,1}和{2,2}
  • 当n=5时,8种方案:{1,1,1,1,1}和{1,1,1,2}和{1,1,2,1}和{1,2,1,1}和{1,2,2}和{2,1,1,1}和{2,1,2}和{2,2,1}
  • 总结:好像有点规律了,是斐波那契数列。递推公式:dp[i] = dp[i-1]+dp[i-2]:dp数组含义是到第(i+1)层时有几种方案,下标i含义是这是第i+1层。

思路1【动态规划法】

  1. 很明显,动态规划:一个状态可以由之前的状态推导而出,应该用动态规划
  • 明确dp数组含义和下标含义:已经指出;
  • 递推公式:已经指出;
  • 初始化:dp[0] = 1;第一层台阶有一种方案。dp[1] = 2;到2层台阶有2中方案;
  • 遍历顺序:从前往后。

代码实现【动态规划法】

class Solution {
public:int climbStairs(int n) {if(n <= 2) return n;vector<int> dp(n,0);//下标i代表到第i+1层台阶,值代表到i+1层台阶有几种方案//初始化dp[0] = 1;//n=1时,1种方案dp[1] = 2;//n=2时,2种方案//遍历顺序for(int i = 2;i < n;i++){//递推公式dp[i] = dp[i-1]+dp[i-2];}return dp[n-1];}
};状态压缩
class Solution {
public:int climbStairs(int n) {if(n <= 2) return n;int dp[2];//初始化dp[0] = 1;//n=1时,1种方案dp[1] = 2;//n=2时,2种方案//遍历顺序for(int i = 2;i < n;i++){int sum = dp[0]+dp[1];dp[0] = dp[1];dp[1] = sum;}return dp[1];}
};

思路2 【递归】

  1. 能用动态规划法,这是记录 六十九【509. 斐波那契数】中提到递归也可以。通过状态递推公式可以认为在重复执行一段代码。

代码实现【递归法】

逻辑没有问题,但是无法通过。因为超出时间限制

class Solution {
public:int climbStairs(int n) {//终止条件if(n <= 2) return n;//单层逻辑return climbStairs(n-1)+climbStairs(n-2);}
};

思路3【回溯法】

  1. 回溯用在组合问题。从一个集合中选择符合条件的元素形成组合可以用。在分析题目时,画树形图判断有几种方案如下:
    在这里插入图片描述
  2. 所以回溯解决办法:每一次都从[1,2]中选择元素加入temp,当组合元素之和是n时符合条件。大于n时停止。

代码实现【回溯法】

逻辑没有问题,但是无法通过。因为超出时间限制

class Solution {
public:void backtracking(int n,int& sum,vector<int>& temp,int& result){//终止条件if(sum == n){result++;return;}if(sum > n){//顶多走n个台阶。超出n就可以停止搜索了return;}//在[1,2]两种走法中选择for(int i = 1;i <= 2;i++){temp.push_back(i);sum += i;backtracking(n,sum,temp,result);sum -= i;temp.pop_back();}return;}int climbStairs(int n) {int result = 0;vector<int> temp;int sum = 0;backtracking(n,sum,temp,result);return result;}
};

“超出时间限制”错误分析

这和算法的性能相关,有以下参考链接讲解了时间复杂度和空间复杂度。

  1. 第一篇:什么是时间复杂度?内容总结:
    在这里插入图片描述
  2. 算法为什么会超时?内容总结:
    认为力扣判断超时是因为计算超过了1s。给出如何测试O(n)、O(n^2)、O(nlogn)的1s计算规模。
    • 个人pc,执行O(n)算法,1s内处理n=8*108在这里插入图片描述
    • 执行O(n^2)算法,1s内处理n=27500.在这里插入图片描述
    • 执行O(nlogn)算法,1s内处理n=2.8*107在这里插入图片描述
  3. 递归算法求斐波那契数列算法复杂度分析内容总结:
  • 递归算法的时间复杂度是:递归的次数*每次递归的时间复杂度
  • 斐波那契数列每次递归的时间复杂度是O(1),常数级别。因为操作单元就是return n。或者深入递归。所以接下来,需要递归多少次?
  • 举个例子:深度为k的二叉树,最多有2k-1个节点。每个节点都是一次递归。那么输入n,递归n-1层。所以最多有2(n-1)-1个节点,所以需要递归2(n-1)-1次。
    在这里插入图片描述
  • 递归求斐波那契数列的时间复杂度是O(2n)。这是代码无法通过的根本原因。在本地环境测试下时间:发现随着n的增加,执行时间的增长速度符合指数级别。在n=43时,超过1s。同理,回溯的逻辑也没有问题,但是时间复杂度同理。
    在这里插入图片描述
  • 如何改进递归算法?减少递归的调用次数。
    递到下一层,修改的是first和second两个参数。在传递的过程中,就已经开始求和计算初始输入(1,2,n);
    class Solution {
    public:int climbStairs(int first,int second,int n) {//first放climbStairs(n-2)的值,second放climbStairs(n-1)的值//终止条件if(n==1 || n == 2) return n;else if(n ==3) return first+second;else {return climbStairs(second,first+second,n-1);}}
    };
    
    该代码求时间复杂度:对输入n,递归次数是n-3。当递归减到3时停止,所以操作执行次数是n-3。时间复杂度是O(n)。用这个递归测试一下时间,明显改进:
    在这里插入图片描述
  • 递归算法的空间复杂度是:递归的次数*每次递归的空间复杂度
  • 递归求斐波那契数列,输入n,递归次数是n。每次递归开辟的空间是相同的,常数级别,O(1)。所以 递归求斐波那契数列的空间复杂度是O(n)
  • 至此,可以总结:虽然求菲波那切数列有递归法(回溯法)、动态规划法。为什么参考把这道题放到动态规划章节。
    在这里插入图片描述
  1. 第四篇:什么是空间复杂度?内容总结:
    在这里插入图片描述
  2. 第五篇:程序执行需要消耗多少内存? 和语言的内存管理相关。
    在这里插入图片描述

三、参考学习

70. 爬楼梯 参考学习链接

学习内容

    1. 爬楼梯的思路和实现在分析题目中已经指出。dp[0]在参考中起始没有含义。所以我的实现中下标i和楼梯层数是错位的。注意初始化
  1. 扩展题目:70. 爬楼梯(进阶版)于下一记录发出。

总结

本文分析了爬楼梯的多种思路,对于递归法导致超时问题,在时间复杂度和空间复杂度方面进行分析。

掌握:如何推出状态转移公式?如何计算一个算法的时间复杂度和空间复杂度?

(欢迎指正,转载标明出处)


http://www.ppmy.cn/news/1506331.html

相关文章

python机器人编程——开发一个pymatlab工具箱(上)

目录 一、前言二、实现过程2.1 封装属性2.2 数据流化显示2.3 输入数据的适应性 三、核心代码说明3.1 设置缓存3.2 随机信号3.3 根据设置绘图 五、总结四、源码PS.扩展阅读ps1.六自由度机器人相关文章资源ps2.四轴机器相关文章资源ps3.移动小车相关文章资源 一、前言 我们知道m…

rm命令学习

删除文件 rm rm命令&#xff08;remove的简写&#xff09;用来删除文件。这条命令会彻底地删除文件&#xff0c;文件将不复存在。Linux命令行可没有“垃圾箱”或“回收站”之类的东西。shell缺少一个恢复删除文件的命令&#xff0c;最好一开始就小心些。 如果你想确保绝对没有…

低代码开发:机遇与挑战

目录 一、什么是低代码开发&#xff1f; 二、低代码开发的机遇 1. 加速开发周期 2. 降低开发门槛 3. 提高生产效率 三、低代码开发的挑战 1. 定制化限制 2. 技术债务累积 3. 安全性问题 四、低代码开发如何改变开发者的工作方式&#xff1f; 1. 专注业务逻辑 2. 团队…

Gdao v1.1.0:Go语言高效ORM框架全面解析

简介:gdao是一种创新的持久层解决方案。主要目的在于 减少编程量&#xff0c;提高生产力&#xff0c;提高性能&#xff0c;支持多数据源整合操作&#xff0c;支持数据读写分离&#xff0c;制定持久层编程规范。 灵活运用gdao&#xff0c;可以在持久层设计上&#xff0c;减少30%…

Linux: security: openssh: v9.8 的一个小改动

这个改动,相对于之前的版本,产生的变化是per-session相关的进程名称,由sshd变成了sshd-session。如果有应用依赖于这个进程名称,就需要注意了。 https://www.openssh.com/releasenotes.html#9.8p1 * sshd(8): the server has been split into a listener binary, sshd(8),a…

Java高级Day23-HashMap

74.HashMap Map接口常用实现类&#xff1a;HashMap、Hashtable和Properties HashMap是Map接口使用频率最高的实现类 HashMap是以key-value对的方式来存储数据 key不能重复&#xff0c;但是值可以重复&#xff0c;允许使用null健和null值 如果添加相同的key&#xff0c;会覆…

交换机常用的贴片网络变压器,滤波器H5084NL / H82409S

华强盛电子导读千兆交换机&#xff1a; 199/2643/0038 在交换机行业中&#xff0c;常用的贴片网络变压器和滤波器型号会根据具体的应用需求、性能指标、成本考量等因素而有所不同。通常&#xff0c;这些器件需要满足网络通信中的高频传输、阻抗匹配、信号隔离、电磁兼容&…

5个适用于Linux系统的PDF转Word工具

凭借其跨平台和设备的统一标准、兼容性和规模小巧等主要优点&#xff0c;可携带文档格式&#xff08;PDF&#xff09;可谓最主流的文件格式之一。 市面上有许多查看PDF文件的强大工具&#xff0c;因此所有Linux系统的用户都可以根据自身喜好找到合适的PDF查看工具。然而&#x…