【动态规划算法题记录】70. 爬楼梯——递归/动态规划

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

题目分析

递归法(超出时间限制)

在这里插入图片描述

  1. 递归参数与返回值
    void reversal(int i, int k)
    每次我们处理第i个台阶到第k个台阶之间的可能性。这里我把结果int cnt放在类成员中了,所以直接在函数中进行处理,不用返回。
  2. 递归终止条件
    当我们处理到最上面的台阶了,也就是reversal(n, n)就可以结束当前递归。
  3. 单层递归逻辑
    单层递归中,我们再将区间(i, k)细分下去:因为我们每次只能上一级或两级台阶,并且上了台阶之后才能处理更高层的范围,所以在缩小范围时,我们针对的是区间的左边。也就是:
for(int j = 1; j <= (k-i) && j <=2; j++){reversal(i+j, k);}

其中,j就是我们上台阶的可能性,它的取值要小于等于2不能超过区间的大小

最终的cpp递归代码:

class Solution {
private:int cnt;
public:void reversal(int i, int k){    // 在第i个台阶到第k个台阶之间做决策// 递归终止条件:已经到最上面的台阶,cnt加一并返回if(i == k){cnt++;return;}// 单层递归:从第i个台阶到第k个台阶的可能性// j在这里代表是上几个台阶for(int j = 1; j <= (k-i) && j <=2; j++){reversal(i+j, k);}}int climbStairs(int n) {cnt = 0;reversal(0, n);return cnt;}
};

动态规划

  1. 确定dp数组以及下标的含义
    dp[i]:爬到第i级台阶的方法数量。

  2. 确定递推公式
    dp[i] = dp[i-1] + dp[i-2]

因为我们只有两种上楼梯的方法,也即上一级台阶或两级台阶。试想:

  • 我们上到第i-1级台阶时,共有d[i-1]种方法,再上一级则到达第i级台阶;
  • 我们上到第i-2级台阶时,共有d[i-2]种方法,再上两级则到达第i级台阶;

上到第i级台阶也就两种情况,从第i-1级台阶再上一级,或是从第i-2级台阶再上两级,那么我们上到第i级台阶的方法不就是 dp[i-1] + dp[i-2]。这也说明了每一级台阶的状态是由前面两级台阶决定的

  1. dp数组初始化
    dp[1] = 1;
    dp[2] = 2;

因为第0级台阶不存在,所以我们不必纠结dp[0]的值到底如何初始化。

  1. 确定遍历顺序
    因为dp[i]是由它的前两个数决定,所以我们只能从前往后去遍历。

  2. 举例推导dp数组
    例如当n=5
    dp[1]=1;
    dp[2]=2;
    dp[3] = dp[2] + dp[1] = 3;
    dp[4] = dp[3] + dp[2] = 5;
    dp[5] = dp[4] + dp[3] = 8;

动态规划的cpp代码:

class Solution {
public:int climbStairs(int n) {if(n < 3) return n;// 确定dp数组以及下标含义vector<int> dp(n+1); //dp[i]是到达第i阶楼梯的方法总数// 初始化dp[1] = 1;dp[2] = 2;// 推导for(int i = 3; i <= n; i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/348597.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

redis 一些笔记1

redis 一、redis事务二、管道2.1 事务与管道的区别 三、主从复制3.13.2 权限细节3.3 基本操作命令3.4 常用3.4.1 一主几从3.4.2 薪火相传3.4.3 反客为主 3.5 步骤3.6 缺点 一、redis事务 放在一个队列里&#xff0c;依次执行&#xff0c;并不保证一致性。与mysql事务不同。 命…

一文讲清:bom管理系统是什么?在生产管理中有什么作用?

在制造业中&#xff0c;物料清单&#xff08;Bill of Materials&#xff0c;简称BOM&#xff09;扮演着至关重要的角色。物料清单&#xff08;BOM&#xff09;是制造或维修产品所需的材料、组件和零件的结构化综合列表&#xff0c;以及所需材料的数量、名称、描述和成本。简而言…

4.3 Python 元组类型常用操作及内置方法

文章目录 1. Tuple元组1.1 元组1.2 获取元素1.3 修改元素 2. 类型转换3. 索引取值与切片4. 遍历元组5. 获取长度6. 拼接与复制6.1 元组的拼接6.2 元组元素复制 7. 成员运算8. 统计元素9. 获取索引10. 练习 1. Tuple元组 1.1 元组 特征: 使用小括号括起来, 内部可以存放多个数…

【C++进阶】RBTree封装map与set

1.红黑树的迭代器 1.1 begin() begin()就是红黑树的开头&#xff0c;那么对于红黑树来说按照中序序列是该树的最左节点。 Iterator Begin(){Node* leftMin _root;while (leftMin->_left){leftMin leftMin->_left;}return Iterator(leftMin);} 1.2 end() begin()就是…

【启明智显分享】个位数价格工业HMI芯片:720P@60fps,配备2D加速

我们生活在一个“屏”的时代&#xff0c;工业自动化、智能生活的实现都离不开屏幕的帮助&#xff0c;而对于消费者而言&#xff0c;最大的痛点就是显示屏的画质&#xff0c;一个优质的人机交互界面影响着用户体验&#xff0c;流畅清晰的图像呈现与屏幕的分辨率、刷新率都息息相…

VScode ssh远程连接代码开发XHR failed

一、问题描述 在vscode下载插件Remote-SSH远程连接进行代码开发时&#xff0c;提示 XHR failed 无法建立连接。 二、解决方案 1. 离线下载vscode-server 第一步&#xff1a;vscode菜单栏----帮助----关于----提交后面的一串数字字母即为vscode的 commit_id 第二步&#xff…

uniapp地图导航

我们只需要给图标加一个点击事件 我这里的数据都是动态的&#xff0c;想测试的朋友可以写固定值 然后跳转之后首先会调到选择软件导航 点击导航之后会显示使用哪个app 最后我们选择之后将会直接跳转到app进行导航

Git基础指令(图文详解)

目录 Git概述Git基础指令Linux系统操作指令 Git软件指令1.配置信息2.名称和邮箱3.初始化版本库4.向版本库中添加文件5.修改版本库文件6. 查看版本库文件历史 7.删除文件8.恢复历史文件 Git概述 Git基础指令 Linux系统操作指令 Git是一款免费、开源的分布式版本控制系统&…

028、工具_Pipeline

Redis客户端执行一条命令分为如下四个过程: 1)发送命令 2)命令排队 3)命令执行 4)返回结果 其中1)+4)称为Round Trip Time(RTT,往返时间)。 Pipeline(它能将一组Redis命令进 行组装,通过一次RTT传输给Redis,再将这组Redis命令的执行结果按顺序返回给客户端,图3-…

早知 121私人导航升级新版本, 第一次使用原生dialog标签。

早知121项目介绍说明 早知121 - 一个快速创建私人导航网站。 用途&#xff1a; 创建个人的工作导航&#xff0c;收集常用网址&#xff0c;可贡献给同事。创建个人垂直领域导航 优点&#xff1a; - 不需懂技术&#xff0c;不用维护服务器&#xff0c;维护私人导航收藏站。 网…

express入门03增删改查

目录 1 搭建服务器2 静态文件托管3 引入bootstrap4 引入jquery5 编写后端接口5.1 添加列表查询方法5.2 添加路由5.3 添加数据表格 总结 我们前两篇介绍了如何利用express搭建服务器&#xff0c;如何实现静态资源托管。那利用这两篇的知识点&#xff0c;我们就可以实现一个小功能…

公司面试题总结(五)

25.谈一谈箭头函数与普通函数的区别&#xff0c;箭头函数主要解决什么问题&#xff1f; 箭头函数与普通函数的区别&#xff1a; ⚫ 语法简洁性&#xff1a; ◼ 箭头函数使用>符号定义&#xff0c;省略了 function 关键字&#xff0c;使得语法更为紧凑。 ◼ 对于单行函…

事件、方法实现 on_radioGreen_clicked ,on_chkBoxUnder_clicked,Qfont,QPalette

Vertical Layout 、Horizontal Layout 实验窗体自适应布局 接上篇界面布局&#xff0c; 实验checkBox、radioBox 的事件槽&#xff0c; 使用Qfont组件变更纯文本框QPlainTextEdit中字体的下划线、加粗、斜体效果 使用调色板组QPalette变更纯文本框QPlainTextEdit中文本颜色 UI…

三、网络服务协议

目录 一、FTP&#xff1a;文件传输协议 二、Telnet&#xff1a;远程登录协议 三、AAA认证 四、DHCP 五、DNS 六、PPP协议 七、ISIS协议 一、FTP&#xff1a;文件传输协议 C/S架构&#xff0c;现多用于企业内部的资料共享和网络设备的文件传输&#xff0c;企业内部搭建一…

element table 点击某一行中按钮加载

在Element UI中&#xff0c;实现表格&#xff08;element-table&#xff09;中的这种功能通常涉及到数据处理和状态管理。当你点击某一行的按钮时&#xff0c;其他行的按钮需要动态地切换为加载状态&#xff0c;这可以通过以下步骤实现&#xff1a; 1.表格组件&#xff1a;使用…

手机流畅运行470亿参数大模型,上交大发布PowerInfer-2推理框架,性能提升29倍

苹果一出手&#xff0c;在手机等移动设备上部署大模型迅速成为行业焦点。 目前&#xff0c;移动设备上运行的模型相对较小&#xff08;苹果的是3B&#xff0c;谷歌的是2B&#xff09;&#xff0c;并且消耗大量内存&#xff0c;这在很大程度上限制了其应用场景。 即使是苹果&…

【西瓜书】9.聚类

聚类任务是无监督学习的一种用于分类等其他任务的前驱过程&#xff0c;作为数据清洗&#xff0c;基于聚类结果训练分类模型 1.聚类性能度量&#xff08;有效性指标&#xff09; 分类任务的性能度量有错误率、精度、准确率P、召回率R、F1度量(P-R的调和平均)、TPR、FPR、AUC回归…

20240613解决飞凌的OK3588-C的核心板的USB3.0接口不读U盘的问题

20240613解决飞凌的OK3588-C的核心板的USB3.0接口不读U盘的问题 2024/6/13 15:21 缘起&#xff0c;由于USB3.0的CC芯片在飞凌的OK3588-C的开发板的底板上&#xff0c;一切正常。 如果你单独使用核心板&#xff0c;很容易出现这个问题【省成本没有使用CC芯片】&#xff1a;不读U…

LabVIEW开发CAN通讯协议

在LabVIEW中开发CAN&#xff08;Controller Area Network&#xff09;通讯协议时&#xff0c;需要全面考虑硬件选择、驱动安装、通信配置、错误处理、数据解析和实时性等多个方面。本文详细介绍了在LabVIEW中实现CAN通讯时的关键点和最佳实践&#xff0c;确保系统的稳定性、可靠…

JFrame.setDefaultLookAndFeelDecorated

在java Swing编程中,作为窗体,我们经常编写类继承JFrame,在main方法中进行加载,如下 有一种方法,不用继承JFrame也可以弹窗,代码如下 但是这个跟我们今天的setDefaultLookAndFeelDecorated有什么关系呢,这个设置,必须在new 对象前进行调用,才有装饰效果,如下 说白了…