当前位置: 首页 > news >正文

爬楼梯及其进阶

假设你正在爬楼梯。需要 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 阶
LeetCode链接:https://leetcode.cn/problems/climbing-stairs/description/

爬楼梯

递归

    爬 n 层楼梯的所有方式 f(n) 可以表示为 f(n) = f(n-1) + f(n-2)。因为一次只能爬一层或者两层,因此到第 n 层前仅可能位于第 n-1 层或第 n-2 层。又可将 n-1、n-2 代入 n ,而最底层为 n = 1、 n = 2,即 f(1) = 1、f(2) = 2。可得:

#define MAX_LENGTH = 51;
vector<int> memo(MAX_LENGTH, -1);
int stair(int n) {if (n == 1)return 1;if (n == 2)return 2;if (-1 == memo[n])memo[n] = stair(n - 1) + stair(n - 2);return memo[n];// return stair[n-1] + stair[n-2];
}
class Solution {
public:int climbStairs(int n) { return stair(n); }
};

提交结果:
提交结果

动态规划

     占位

爬楼梯进阶

由于体力有限,一次爬两层后接下来两次每次只能爬一层,你有多少种不同的方法可以爬到楼顶呢?
示例 1:
输入:n = 6
输出:7
解释:第七项中,一次爬两阶后,后续两次只能为一阶。
1. 1 阶 + 1 阶 + 1 阶 + 1 阶 + 1 阶 + 1 阶
2. 2 阶 + 1 阶 + 1 阶 + 1 阶 + 1 阶
3. 1 阶 + 2 阶 + 1 阶 + 1 阶 + 1 阶
4. 1 阶 + 1 阶 + 2 阶 + 1 阶 + 1 阶
5. 1 阶 + 1 阶 + 1 阶 + 2 阶 + 1 阶
6. 1 阶 + 1 阶 + 1 阶 + 1 阶 + 2 阶
7. 2 阶 + 1 阶 + 1 阶 + 2 阶

思路

     在该问题中,当前可爬台阶数受到上一次执行结果的影响,因此需要考虑上一层的状态,为此我的思路是引入额外的变量进行标识。变量 flag 表示在经过几次爬升一阶后可以进行选择爬升阶梯的数量,当 flag > 0 时,每次只能爬一阶,当 flag = 0 时,可以选择下次爬一阶或者爬两阶,如果选择爬两阶需要把 flag 置为2,在起始状态下 flag 的值为0。

long long stair(int n, int flag = 0) {long long v;if (n <= 0)return 0;if (1 == n)return 1;if (2 == n) {if (0 == flag)return 2;elsereturn 1;}if (flag > 0) {v = stair(n - 1, flag - 1);}else {v = stair(n - 1, 0) + stair(n - 2, 2);}return v;
}
算法的运行结果为:
爬升5阶,有:5种方法
爬升6阶,有:7种方法
爬升7阶,有:10种方法
爬升8阶,有:14种方法
爬升9阶,有:19种方法
爬升10阶,有:26种方法
爬升11阶,有:36种方法
爬升12阶,有:50种方法
爬升13阶,有:69种方法
爬升14阶,有:95种方法
爬升15阶,有:131种方法

思考

     怎么使用记忆进行存储,从而避免不必要的计算资源浪费。

http://www.lryc.cn/news/583192.html

相关文章:

  • Kubernetes 存储入门
  • 由 DB_FILES 参数导致的 dg 服务器无法同步问题
  • 搭建一款结合传统黄历功能的日历小程序
  • 汽车智能化2.0引爆「万亿蛋糕」,谁在改写游戏规则?
  • A1220LUA-T Allegro高精度霍尔效应开关 车规+极致功耗+全极触发 重新定义位置检测标准
  • 【Gin】HTTP 请求调试器
  • 微软官方C++构建工具:历史演变、核心组件与现代实践指南
  • Rust与Cypress应用
  • 在Ubuntu上安装配置 LLaMA-Factory
  • 人工智能-基础篇-27-模型上下文协议--MCP到底怎么理解?对比HTTP的区别?
  • AI应用实践:制作一个支持超长计算公式的计算器,计算内容只包含加减乘除算法,保存在一个HTML文件中
  • Apache Tomcat SessionExample 漏洞分析与防范
  • 【AI大模型】PyTorch Lightning 简化工具
  • Node.js 是什么?npm 是什么? Vue 为什么需要他们?
  • Flutter基础(前端教程⑦-Http和卡片)
  • 【数字后端】- Standard Cell Status
  • SQLZoo 练习与测试答案汇总(复杂题有最优解与其他解法分析、解题技巧)
  • Java 各集合接口常用方法对照表
  • 解决SQL Server SQL语句性能问题(9)——SQL语句改写(7)
  • 如何识别SQL Server中需要添加索引的查询
  • nl2sql的解药pipe syntax
  • Linux入门篇学习——Linux 编写第一个自己的命令
  • 一天一道Sql题(day04)
  • 详解Kafka重平衡机制详解
  • Vue+ElementUI聊天室开发指南
  • Vue3 Element plus table有fixed列时错行
  • 7.神经网络基础
  • 【深度学习】【入门】Sequential的使用和简单神经网络搭建
  • 【机器学习】BeamSearch算法
  • 华为OD机试_2025 B卷_观看文艺汇演问题(Python,100分)(附详细解题思路)