爬楼梯(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]; }
总结
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件!
如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
暂无“基于Go和PHP语言实现爬楼梯算法的思路详解”评论...
更新动态
2024年05月06日
2024年05月06日
- 名洋.1990-分手摆在胸口【天下唱片】【WAV+CUE】
- 罗大佑.2018-当年离家的年轻人巡回演唱会【大右音乐】【WAV+CUE】
- 姜育恒.1991-金曲精丫永声】【WAV+CUE】
- 水木年华.2010-启程【英皇星艺】【WAV+CUE】
- 邓丽君《漫步人生路》[DSF][1.3G]
- 林俊杰《学不会》[DSF][1.3G]
- 费玉清《Ultimate Sound》SACD 限量版[DSF][2G]
- 杨耀东.2002-经典金曲珍藏版2CD【东尼机构】【WAV+CUE】
- 新民樂演奏《春来人不来上海管弦楽團伴奏》[WAV+CUE].
- 玛吉阿米藏族民间歌舞艺术团-《仓央嘉措之歌》[ADMS][WAV+CUE]
- 王心凌《爱你》[FLAC][836M]
- 叶少菲《纯爱沉思录》[320K/MP3][120.43MB]
- 叶少菲《纯爱沉思录》[FLAC/分轨][330.3MB]
- 电子琴《汽车音响精品第三集第四集第五集》特效360度[WAV+CUE]
- 新民樂演奏《春来人不来上海管弦楽團伴奏》[WAV+CUE