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

三斤和他的喵的个人博客 / 249 / 4 / 创建于 3年前 / 更新于 3年前

爬楼梯（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...

算法数据结构 leetcode

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

三斤

三斤和他的喵

课程读者 172 声望

一个PHPer的修行之路。欢迎大家关注我的公众号《三斤和他的喵》

3 人点赞

你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程，JWT 概念及使用和 API 开发相关的进阶知识。

以构建论坛项目 LaraBBS 为线索，展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。

推荐文章：

更多推荐...

面试 POPER 的后端开发工程师的离奇经历 35 / 104 |

分享创造

📙《高并发的哲学原理》开源图书发布十一天 star 数已经破千！ 47 / 16 |

博客

PHP面试高薪宝典系列: 常见基础算法（附完整代码） 23 / 3 |

博客

强一致性的分布式事务几种模式对比（php有了新方案） 33 / 20 |

博客

PHP实现汉诺塔算法 21 / 9 |

博客

PHP使用动态规划实现最优红包组合 33 / 5 |

讨论数量: 4

yzh52521

33 声望

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];
        }

3年前评论

三斤和他的喵（楼主）

优秀 :+1:

captain2021

NB

captain2021

Laravel 5.8 译者 422 声望 / 开发 @ 谈笑风生

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

3年前评论

三斤和他的喵（楼主）

后续会专门写这个事情

captain2021 （作者）

@三斤和他的喵期待

captain2021 （作者）

@hxd 还有那个金矿开采的问题，怎样都想不通了，说是动态规划的一个应用，大佬那个有什么指点的吗

zpers

动态规划的重点就是状态转移，说白了就是结果转移成数据规模更小的结果，n=n-1+k，每种题目的k都不一样，但是在当前题目中这个k是固定的，所以这个式子也可以看成是一个等差数列，差说就是k（不知道有没有解释清楚，如果有什么没解析清楚你可以提出来，我表达清楚一点）

zpers

还有一种就是上面说的斐波那契数列，f(n) = f(n-1)+f(n-2) , 这种就是你想得到n的结果，只需要前两种结果相加就可以，这也是状态转移；；；；；；
例如：给出一串数字求通向式：1，2，3，5，8，13，21…….，求出通向式.
通向式：f(n)= f(n-1)+f(n-2); (n > 2),

captain2021 （作者）

@zpers 怎样确定结果和之前的关联啊，挖金矿的我都没想通为啥前面和后面的关联

Aliliin

课程读者 512 声望 / Phper @ 转 Goer

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];
}

3年前评论

三斤和他的喵（楼主）

优秀 :+1:

Aliliin （作者）

@三斤和他的喵优秀不给点个赞。😂

取名字好烦。

0 声望

期待将动态规划

3年前评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

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

爬楼梯（Climbing-Stairs）

解题思路

代码实现

GO 语言实现

总结

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

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

爬楼梯（Climbing-Stairs）

解题思路

代码实现

GO 语言实现

总结

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录