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

zhubaba2019

今日一题：

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

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

fule

我简单题都刷不明白

zhubaba2019

哦嚯！没人感兴趣啊。

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

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

咸鱼咸鱼

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

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

因为太简单了……

zhubaba2019

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

那明天来难的

Swag

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

手握键盘

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

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

buste

dp, 随便做

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

可乐呀

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