让我们一起啃算法----爬楼梯

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

总结

每天进步一点点,加油!
算法教程项目,每天更新一题,点个 star 支持一下呀
github.com/wx-satellite/learning-a...

本作品采用《CC 协议》,转载必须注明作者和本文链接

三斤

《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
讨论数量: 4
function climbStairs($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];
        }
2周前 评论
三斤和他的喵 (楼主) 2周前
hxd 2周前
hxd

动态规划的场景只有是结果和前两个相关的吗?还是什么情况能用动态规划啊

2周前 评论
三斤和他的喵 (楼主) 2周前
hxd (作者) 2周前
hxd (作者) 2周前
zpers 6天前
zpers 6天前
hxd (作者) 5天前
function climbStairs($n) {
    if ($n <= 2) return $n;
    $dp = [1 => 1, 2 => 2];
    for ($i = 3; $i <= $n; $i++) {
        $dp[$i] = $dp[$i - 1] + $dp[$i - 2];
    }
    return $dp[$n];
}
2周前 评论
三斤和他的喵 (楼主) 1周前
Ali (作者) 1周前

期待将动态规划

1周前 评论

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!