基于Go和PHP语言实现爬楼梯算法的思路详解

爬楼梯（Climbing-Stairs）

题干：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：  输入： 2  输出： 2  解释： 有两种方法可以爬到楼顶。  1. 1 阶 + 1 阶  2. 2 阶示例 2：  输入： 3  输出： 3  解释： 有三种方法可以爬到楼顶。  1. 1 阶 + 1 阶 + 1 阶  2. 1 阶 + 2 阶  3. 2 阶 + 1 阶来源：力扣

这题爬楼梯算是算法题里面比较经典的。

解题思路

这题的解题思路主要有两种：

1.动态规划

2.斐波那契数列

动态规划算是一个比较重要的解题技巧与思路，后续我会写一系列需要用动态规划思路解题的文章，帮助大家更好的理解动态规划。

这题我们用斐波那契数列来解。

斐波那契数列又称兔子数列，指得是：1、1、2、3、5、8、13、21、……，在数学上它得递推公式是：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）。

放到这个题目中我们可以发现：二阶楼梯的走法有 2种： 1 阶 + 1 阶 、 2 阶三阶楼梯的走法有 3种：1 阶 + 1 阶、1 阶 + 2 阶、2 阶 + 1 阶四阶楼梯的走法有 5种：1 阶 + 1 阶 + 1 阶 + 1 阶、1 阶 + 2 阶 + 1 阶、1 阶 + 1 阶 + 2 阶、2 阶 + 2 阶、2 阶 + 1 阶 + 1 阶……

综上，我们可以发现 n 阶楼梯有 m 种爬法，且 m 符合斐波那契数列规律，所以直接上代码咯！

Go 实现

// 斐波那契数列
// 1 1 2 3 5 8 13 ....
func climbStairs2(n int) int {
 // 1 阶台阶直接返回 1
 if n == 1 {
  return 1
 }
 // 2 阶台阶直接返回 2
 if n == 2 {
  return 2
 }
 current := 2
 pre := 1
 // 当前台阶的走法是前两个台阶走法之和
 for i := 3; i <= n;i ++ {
  current = current + pre
  pre = current - pre
 }
 return current
}

PHP 实现，一共两版实现，看自己喜欢哪种代码吧

function climbStairs($n) {
 // if($n==1) return 1;
 // $dp[1]=1;
 // $dp[2]=2;
 // for($i=3;$i<=$n;$i++){
 //  $dp[$i]=$dp[$i-1]+$dp[$i-2];
 // }
 //
 // return $dp[$n];

 if($n <= 2) return $n;
 $dp = [1 => 1,2 => 2];
 foreach(range(3,$n+1) as $v){
  //递归加法，这个爬楼梯就是斐波拉切算法求最后f(n-1)+f(n-2)的和
  $dp[$v] = $dp[$v-1] + $dp[$v-2];
 }

 return $dp[$n];
}

总结

到此这篇关于基于Go和PHP语言实现爬楼梯算法的思路详解的文章就介绍到这了,更多相关Go PHP 爬楼梯算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言项目爬楼梯的两种实现方法参考

    [项目-爬楼梯] 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法? [参考解答(递归法)] 基础:楼梯有一个台阶,只有一种走法(一步登上去):两个台阶,有2种走法(一步上去,或分两次上去): 递推:有n个台阶时,设有count(n)种走法,最后一步走1个台阶,有count(n-1)种走法:最后一步走2个台阶,有count(n-2)种走法.于是count(n)=count(n-1)+count(n-2). 可见,此问题的数学模型竟然是斐波那契数. #incl

  • Python使用回溯法子集树模板解决爬楼梯问题示例

    Python使用回溯法子集树模板解决爬楼梯问题示例

    本文实例讲述了Python使用回溯法子集树模板解决爬楼梯问题.分享给大家供大家参考,具体如下: 问题 某楼梯有n层台阶,每步只能走1级台阶,或2级台阶.从下向上爬楼梯,有多少种爬法? 分析 这个问题之前用分治法解决过.但是,这里我要用回溯法子集树模板解决它. 祭出元素-状态空间分析大法:每一步是一个元素,可走的步数[1,2]就是其状态空间.不难看出,元素不固定,状态空间固定. 直接上代码. 代码 '''爬楼梯''' n = 7 # 楼梯阶数 x = [] # 一个解(长度不固定,1-2数组,表示

  • Python3爬楼梯算法示例

    本文实例讲述了Python3爬楼梯算法.分享给大家供大家参考,具体如下: 假设你正在爬楼梯.需要 n 步你才能到达楼顶. 每次你可以爬 1 或 2 个台阶.你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数. 方案一:每一步都是前两步和前一步的和 class Solution(object): def climbStairs(self, n): """ :type n: int :rtype: int """ pre, cur =

  • 基于Go和PHP语言实现爬楼梯算法的思路详解

    爬楼梯(Climbing-Stairs) 题干: 假设你正在爬楼梯.需要 n 阶你才能到达楼顶.每次你可以爬 1 或 2 个台阶.你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数.示例 1:  输入: 2  输出: 2  解释: 有两种方法可以爬到楼顶.  1. 1 阶 + 1 阶  2. 2 阶示例 2:  输入: 3  输出: 3  解释: 有三种方法可以爬到楼顶.  1. 1 阶 + 1 阶 + 1 阶  2. 1 阶 + 2 阶  3. 2 阶 + 1 阶来源:力扣 这题

  • R语言关于随机森林算法的知识点详解

    在随机森林方法中,创建大量的决策树. 每个观察被馈入每个决策树. 每个观察的最常见的结果被用作最终输出. 新的观察结果被馈入所有的树并且对每个分类模型取多数投票. 对构建树时未使用的情况进行错误估计. 这称为OOB(袋外)误差估计,其被提及为百分比. R语言包"randomForest"用于创建随机森林. 安装R包 在R语言控制台中使用以下命令安装软件包. 您还必须安装相关软件包(如果有). install.packages("randomForest") 包&qu

  • 基于Numpy.convolve使用Python实现滑动平均滤波的思路详解

    基于Numpy.convolve使用Python实现滑动平均滤波的思路详解

    ​ 1.滑动平均概念 滑动平均滤波法(又称递推平均滤波法),时把连续取N个采样值看成一个队列 ,队列的长度固定为N ,每次采样到一个新数据放入队尾,并扔掉原来队首的一次数据.(先进先出原则)  把队列中的N个数据进行算术平均运算,就可获得新的滤波结果.N值的选取:流量,N=12:压力:N=4:液面,N=4~12:温度,N=1~4 优点:  对周期性干扰有良好的抑制作用,平滑度高  适用于高频振荡的系统 缺点:  灵敏度低  对偶然出现的脉冲性干扰的抑制作用较差  不易消除由于脉冲干扰所引起的采样

  • Go基于GORM 获取当前请求所执行的 SQL 信息(思路详解)

    Go基于GORM 获取当前请求所执行的 SQL 信息(思路详解)

    前言 为了便于精准排查问题,需要将当前的请求信息与当前执行的 SQL 信息设置对应关系记录下来,记录的 SQL 信息包括: 执行 SQL 的当前时间: 执行 SQL 的文件地址和行号: 执行 SQL 的花费时长: 执行 SQL 的影响行数: 执行的 SQL 语句: 数据库组件使用的是GORM. 思路 1.在执行 SQL 前,设置开始执行时间(计算执行时长会用到): 2.在执行 SQL 后,第一,获取当前请求的上下文,为什么获取上下文,因为需要从上下文中获取本次请求信息,第二,获取 SQL 执行前

  • 基于C语言实现计算生辰八字五行的示例详解

    本文介绍生辰八字和八字五行的一种算法.站内有人在查询生辰八字的算法,此题本人也感兴趣.故以此文以续貂尾. 生辰八字计算要点是节气日,年柱以立春起,月柱以是月节气日起,故先要计算月首的节气日.本节气算法的节气时刻精度差些,但确定节气日是可以的.程序启动时先计算干支表和对应的五行表.具体的计算方法参阅程序的注释.算法很简单,一看就明白.要注意的是,八字的时柱先输出的是起时,生日时辰十二个时辰对应下面的起时表计算.程序列示文本打印输出和图片显示输出二种方法供参考. 本文主要介绍生辰八字的算法,没有计算

  • 基于Python_脚本CGI、特点、应用、开发环境(详解)

    基于Python_脚本CGI、特点、应用、开发环境(详解)

    CGI CGI 目前由NCSA维护,NCSA定义CGI如下: CGI(Common Gateway Interface),通用网关接口,它是一段程序,运行在服务器上如:HTTP服务器,提供同客户端HTML页面的接口. CGI程序可以是Python脚本.Perl脚本.Shell脚本.C或者C++程序等. 服务器 在你进行CGI编程前,确保您的Web服务器支持CGI及已经配置了CGI的处理程序. 所有的HTTP服务器执行CGI程序都保存在一个预先配置的目录.这个目录被称为CGI目录,并按照惯例,它被

  • 基于java变量和作用域以及成员变量的默认初始化(详解)

    ava中的变量有成员变量和局部变量,定义在类中方法之外的变量成为成员变量或者成员字段(域),表示一个类所具有的属性,定义为类的成员变量的变量的作用于是整个类,该变量在定义的时候不需要初始化,在使用前java会自动初始化成员变量,对于基本数据类型的的自动初始化如下: java基本类型默认初始化值 int 0 short 0 byte 0 long 0 float 0.0 double 0.0 boolean false char 0 例如: public class test{ private i

  • 基于C#调用c++Dll结构体数组指针的问题详解

    C#调用c++dll文件是一件很麻烦的事情,首先面临的是数据类型转换的问题,相信经常做c#开发的都和我一样把学校的那点c++底子都忘光了吧(语言特性类). 网上有一大堆得转换对应表,也有一大堆的转换实例,但是都没有强调一个更重要的问题,就是c#数据类型和c++数据类型占内存长度的对应关系. 如果dll文件中只包含一些基础类型,那这个问题可能可以被忽略,但是如果是组合类型(这个叫法也许不妥),如结构体.类类型等,在其中的成员变量的长度的申明正确与否将决定你对dll文件调用的成败. 如有以下代码,其

  • 使用Go基于WebSocket构建千万级视频直播弹幕系统的代码详解

    (1)业务复杂度介绍 开门见山,假设一个直播间同时500W人在线,那么1秒钟1000条弹幕,那么弹幕系统的推送频率就是: 500W * 1000条/秒=50亿条/秒 ,想想B站2019跨年晚会那次弹幕系统得是多么的NB,况且一个大型网站不可能只有一个直播间! 使用Go做WebSocket开发无非就是三种情况: 使用Go原生自带的库,也就是 golang.org/x/net ,但是这个官方库真是出了奇Bug多 使用GitHub大佬 gorilla/websocket 库,可以结合到某些Web开发框

随机推荐