白云岛资源网 Design By www.pvray.com

爬楼梯(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];
}

总结

白云岛资源网 Design By www.pvray.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
白云岛资源网 Design By www.pvray.com

《魔兽世界》大逃杀!60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容,新游玩模式《强袭风暴》即将于3月21 日在亚服上线,届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕,并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时,他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中,玩家将会进入一个全新的海盗主题大逃杀式限时活动,其中包含极高的风险和史诗级的奖励。

《强袭风暴》不是普通的战场,作为一个独立于主游戏之外的活动,玩家可以用大逃杀的风格来体验《魔兽世界》,不分职业、不分装备(除了你在赛局中捡到的),光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式,玩家在加入海盗主题的预赛大厅区域前,可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹,《巨龙崛起》和《魔兽世界:巫妖王之怒 经典版》的玩家都可以获得奖励。