全球主机交流论坛

标题: 20201218-学好算法，大厂996不是梦-爬楼梯 [打印本页]

作者: zhubaba2019 时间: 2020-12-18 13:52
标题: 20201218-学好算法，大厂996不是梦-爬楼梯
今日一题：

假设你正在爬楼梯。需要 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

作者: fule 时间: 2020-12-18 13:55

我简单题都刷不明白

作者: ruans 时间: 2020-12-18 14:05
没学历啥大厂都进不了兄嘚

作者: zhubaba2019 时间: 2020-12-18 15:30
哦嚯！没人感兴趣啊。

这个是个动态规划的问题。
我们可以想象如果我们在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

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

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

因为太简单了……

作者: zhubaba2019 时间: 2020-12-18 15:49

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

那明天来难的

作者: Swag 时间: 2020-12-18 16:17
动态规划f(n) = f(n-1) + f(n-2)

作者: 手握键盘 时间: 2020-12-18 16:22

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

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

作者: buste 时间: 2020-12-18 16:23
本帖最后由 buste 于 2020-12-18 16:25 编辑

dp, 随便做

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

作者: 可乐呀 时间: 2020-12-18 23:22
这个简单，最简单的DP/记忆化搜索

作者: 1652291305 时间: 2020-12-18 23:30
这个dp是不是太简单了

作者: xcpan710 时间: 2020-12-19 00:22
动态规划加状态存储

作者: yisuo 时间: 2020-12-19 01:34
提示: 作者被禁止或删除内容自动屏蔽

欢迎光临全球主机交流论坛 (https://443502.xyz/)