20201218-学好算法，大厂996不是梦-爬楼梯

zhubaba2019 · 发表于 2020-12-18 13:52:53

今日一题：

假设你正在爬楼梯。需要 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 阶

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

ruans · 发表于 2020-12-18 14:05:49

没学历啥大厂都进不了兄嘚

fule · 发表于 2020-12-18 13:55:51

我简单题都刷不明白

zhubaba2019 · 发表于 2020-12-18 15:30:38

哦嚯！没人感兴趣啊。

这个是个动态规划的问题。
我们可以想象如果我们在N阶，那么我们要么从n-1阶爬上去，要么从n-2阶爬上去。状态方程为
f(n) = f(n-1) + f(n-2)

因为已知n=2时返回2， n=3时返回3. 所以可以依次得出f(n)

咸鱼咸鱼 · 发表于 2020-12-18 15:37:26

zhubaba2019 发表于 2020-12-18 15:30
哦嚯！没人感兴趣啊。

这个是个动态规划的问题。

因为太简单了……

zhubaba2019 · 发表于 2020-12-18 15:49:25

咸鱼咸鱼发表于 2020-12-18 15:37
因为太简单了……

那明天来难的

Swag · 发表于 2020-12-18 16:17:43

动态规划f(n) = f(n-1) + f(n-2)

手握键盘 · 发表于 2020-12-18 16:22:53

ruans 发表于 2020-12-18 14:05
没学历啥大厂都进不了兄嘚

别那么绝望我同学大专进了一家小游戏公司，后来被TX收购了，现在正式安卓开发

buste · 发表于 2020-12-18 16:23:19

本帖最后由 buste 于 2020-12-18 16:25 编辑

dp, 随便做

要考mjj你至少得来个3维dp配AC自动机+神经搜索树吧

可乐呀 · 发表于 2020-12-18 23:22:55

这个简单，最简单的DP/记忆化搜索

		自动登录	找回密码
密码			注册

[疑问] 20201218-学好算法，大厂996不是梦-爬楼梯