基于Go和PHP语言如何实现爬楼梯算法
导读:本文共1532.5字符,通常情况下阅读需要5分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 爬楼梯(Climbing-Stairs)题干:假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数。示例 1:输入: 2输出: 2解释: 有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶示例 2:输入: 3输出: 3解释: 有三种方法可以爬到楼顶。1. 1 阶... ...
目录
(为您整理了一些要点),点击可以直达。爬楼梯(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 实现
PHP 实现,一共两版实现,看自己喜欢哪种代码吧
基于Go和PHP语言如何实现爬楼梯算法的详细内容,希望对您有所帮助,信息来源于网络。