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

2024-06-13 18:04

本文主要是介绍【动态规划算法题记录】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];}
};

这篇关于【动态规划算法题记录】70. 爬楼梯——递归/动态规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1058026

相关文章

Python MySQL如何通过Binlog获取变更记录恢复数据

《PythonMySQL如何通过Binlog获取变更记录恢复数据》本文介绍了如何使用Python和pymysqlreplication库通过MySQL的二进制日志(Binlog)获取数据库的变更记录... 目录python mysql通过Binlog获取变更记录恢复数据1.安装pymysqlreplicat

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

VUE动态绑定class类的三种常用方式及适用场景详解

《VUE动态绑定class类的三种常用方式及适用场景详解》文章介绍了在实际开发中动态绑定class的三种常见情况及其解决方案,包括根据不同的返回值渲染不同的class样式、给模块添加基础样式以及根据设... 目录前言1.动态选择class样式(对象添加:情景一)2.动态添加一个class样式(字符串添加:情

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R

Servlet中配置和使用过滤器的步骤记录

《Servlet中配置和使用过滤器的步骤记录》:本文主要介绍在Servlet中配置和使用过滤器的方法,包括创建过滤器类、配置过滤器以及在Web应用中使用过滤器等步骤,文中通过代码介绍的非常详细,需... 目录创建过滤器类配置过滤器使用过滤器总结在Servlet中配置和使用过滤器主要包括创建过滤器类、配置过滤

如何用Python绘制简易动态圣诞树

《如何用Python绘制简易动态圣诞树》这篇文章主要给大家介绍了关于如何用Python绘制简易动态圣诞树,文中讲解了如何通过编写代码来实现特定的效果,包括代码的编写技巧和效果的展示,需要的朋友可以参考... 目录代码:效果:总结 代码:import randomimport timefrom math

正则表达式高级应用与性能优化记录

《正则表达式高级应用与性能优化记录》本文介绍了正则表达式的高级应用和性能优化技巧,包括文本拆分、合并、XML/HTML解析、数据分析、以及性能优化方法,通过这些技巧,可以更高效地利用正则表达式进行复杂... 目录第6章:正则表达式的高级应用6.1 模式匹配与文本处理6.1.1 文本拆分6.1.2 文本合并6

python与QT联合的详细步骤记录

《python与QT联合的详细步骤记录》:本文主要介绍python与QT联合的详细步骤,文章还展示了如何在Python中调用QT的.ui文件来实现GUI界面,并介绍了多窗口的应用,文中通过代码介绍... 目录一、文章简介二、安装pyqt5三、GUI页面设计四、python的使用python文件创建pytho

Java中JSON字符串反序列化(动态泛型)

《Java中JSON字符串反序列化(动态泛型)》文章讨论了在定时任务中使用反射调用目标对象时处理动态参数的问题,通过将方法参数存储为JSON字符串并进行反序列化,可以实现动态调用,然而,这种方式容易导... 需求:定时任务扫描,反射调用目标对象,但是,方法的传参不是固定的。方案一:将方法参数存成jsON字

.NET利用C#字节流动态操作Excel文件

《.NET利用C#字节流动态操作Excel文件》在.NET开发中,通过字节流动态操作Excel文件提供了一种高效且灵活的方式处理数据,本文将演示如何在.NET平台使用C#通过字节流创建,读取,编辑及保... 目录用C#创建并保存Excel工作簿为字节流用C#通过字节流直接读取Excel文件数据用C#通过字节