这是一个创建于 1612 天前的主题，其中的信息可能已经有所发展或是发生改变。
原题： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
变形： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 或 3 个台阶，且每次上的台阶不相同。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
哥哥们 这个变形 怎么解答 ？ 怎么个思路 ？
 |
1
hejw19970413 OP 有没有大佬可以试着解决一下 ，弟弟想了一宿没思路
|
 |
2
hello2060 2020-06-12 11:05:40 +08:00
很难吗？开一个数组 int ways[n + 1], 答案是 ways[n] 初始化 ways[0] = 1, ways[1] = 1, ways[2] = 2, ways[3] = xx, ways[n] = ways[n - 1] + ways[n - 2] + ways[n - 3] ? 什么叫每次上的台阶不同
|
 |
3
Vegetable 2020-06-12 11:05:41 +08:00
什么叫每次上的台阶不同？还能有相同的？
|
 |
4
winterfell30 2020-06-12 11:08:53 +08:00  1
斐波那契数列
|
|
5
Vegetable 2020-06-12 11:10:27 +08:00
有点读懂了，试说每次上的台阶数不能与上一步相同？这个也算变种吗？可以说这是变了个数吧
|
 |
6
VoidChen 2020-06-12 11:11:43 +08:00
我想问下有没有好的刷 leecode 的总结。。之前在 github 看到一个按算法类型来分类的，我不知道保存到哪没了。。
|
 |
7
cheese 2020-06-12 11:15:09 +08:00
|
 |
8
leavan 2020-06-12 11:16:04 +08:00
哦我懂了，就是其他方法走过一次的楼梯不能再走了呗。那不是很简单吗？从楼顶往回看，最多只有三个台阶可以一步到楼顶，那么我们只需要证明这三种方法都可行就行了，每次都往前各推三步（如果有一个不是三步的，那么势必会造成重复），发现推到边界处仍然不会重复，所以有三种方法。答案就是 3，当然如果你 n 只有 1 或 2 的话那么方法也相应减少。
|
 |
9
coderraven 2020-06-12 11:16:10 +08:00
怎么有点二叉树的感觉
用过 1，那么左右子树就只能是 2 和 3 。 用过 2，那么左右子树就只能是 1 和 3. 用过 3…. 最后再走一波数值和是 n 的遍历？ |
 |
11
zhjy23212 2020-06-12 11:17:40 +08:00
dp 里面每个状态存之前到这个点的步数，下次遍历跳过这几个。
基本上是 frog jump 的变体 |
|
12
hejw19970413 OP @Vegetable 比如 上 2 阶 只可以一次性上 2 级 不能是 1 级 1 级
|
 |
13
EggtartZ 2020-06-12 11:18:59 +08:00
`dp[n, 1] = dp[n - 3, 2] + dp[n - 4, 3]` 这样的意思？
|
|
14
leavan 2020-06-12 11:21:19 +08:00
如果是跟上一步的台阶不同的话，那就动态规划。
``` ways[i][0] = ways[i - 1][1] + ways[i - 1][2] ways[i][1] = ways[i - 2][0] + ways[i - 2][2] ways[i][2] = ways[i - 3][0] + ways[i - 3][1] ``` |
|
15
hello2060 2020-06-12 11:21:36 +08:00
那就不要 int[n + 1] 搞一个数据结构，每一个位置存着 1.到这里的总方法数 2. 前一步是 n-1 的方法书 3.前一步是 n-2 的方法数 4.前一步是 n - 3 的方法数
那你到 n 的方法数 就是 走 2，3 到 n-1 的方法数 + 走 1，3 到 n -2 的方法数 + 走 1，2 到 n-3 的方法数 |
|
16
hejw19970413 OP @hello2060 大佬 你这个第三个不对啊。1+1+2 = 4 第三级 那有 4 种啊 3 ，12 ，21
|
|
17
hello2060 2020-06-12 11:23:58 +08:00
@hejw19970413 第三个我不是没算嘛 xx 反正就那个意思，哈哈
|
|
18
Vegetable 2020-06-12 11:37:50 +08:00
大概想了一下
可以重复的时候，dp(n) = dp(n-1)+dp(n-2)+dp(n-3) 不能重复的话，计算点 n 时，从 n-2 到 n-1 这一点的数据都是要去掉的，n-4 到 n-2 要去掉，n-6 到 n-3 要去掉。 所以 dp(n) = (dp(n-1) - dp(n-2)) + (dp(n-2)-dp(n-4))+(dp(n-3)-dp(n-6)) 是这样吗 |
|
19
hejw19970413 OP @Vegetable 我去跑一下
|
 |
20
xw900812 2020-06-12 11:47:53 +08:00
dynamic programming... YouTube 搜 huahua leetcode 讲这道爬楼梯的问题，很经典的 DP 题目
|
 |
21
buhi 2020-06-12 11:50:28 +08:00
第一个题就是斐波那契数列, 答 dp 的都输了
const stair_ways = n => { return Math.round((1 / sqrt_5) * Math.pow((1 + sqrt_5) / 2, n + 1) - (1 / sqrt_5) * Math.pow((1 - sqrt_5) / 2, n + 1)) } |
 |
22
MoYi123 2020-06-12 11:51:45 +08:00
三个数字的斐波那契数列
|
|
23
EggtartZ 2020-06-12 11:53:45 +08:00
```
def solve(n, m): dp = [[0] * m for i in range(n)] for i in range(m): dp[i][i] = 1 for j in range(i): dp[i][j] = sum(dp[i - j - 1]) - dp[i - j - 1][j] for i in range(m, n): for j in range(m): dp[i][j] = sum(dp[i - j - 1]) - dp[i - j - 1][j] return sum(dp[n - 1]) ``` 大概是这样吧 |
 |
24
mymike 2020-06-12 11:55:21 +08:00 via iPhone
这个和最近的刷房子类似 需要加一个维度
|
 |
25
larisboy 2020-06-12 11:55:24 +08:00
数组+斐波那契数列
|
|
27
buhi 2020-06-12 12:04:10 +08:00
算斐波那契是 O(1), dp 不是 O(1)
|
|
28
hejw19970413 OP @buhi 大佬。按照您的公式算出来 答案不对
|
|
29
hejw19970413 OP @Vegetable 我需要手动算到 6 还是 7 啊
|
 |
30
lxy42 2020-06-12 12:20:03 +08:00
```python
def walk_dp(n): dp = collections.deque([[1, 0, 0], [0, 1, 0], [1, 1, 1]]) for _ in range(3, n): d = [dp[-1][1] + dp[-1][2], dp[-2][0] + dp[-2][2], dp[-3][0] + dp[-3][1], ] dp.append(d) dp.popleft() return sum(dp[-1]) ``` |
|
31
hejw19970413 OP @EggtartZ 您这个 m 是啥？
|
|
32
hejw19970413 OP @lxy42 大佬。您这个从 4 开始都是 3
|
 |
33
levelworm 2020-06-12 12:25:59 +08:00 via Android
这个感觉和分硬币有点像，总共 X 美元，有 5 分，一毛，25 分，50 分以及一美元，求问总共有几种分法。SICP 上第一章有答案。
|
|
34
levelworm 2020-06-12 12:28:47 +08:00 via Android
我直接抄书，我认为这个分硬币和上楼梯是一个事情。
they are calculating the number (N) of ways of change a quatity (A) using K kinds of coins by adding: 1. the number of ways (X) of changing A without coins of the first type. 2.The number of ways (Y) of changing (A - D), where D is the denomination of the fisrt coin, using ALL K types of coins. |
|
35
hejw19970413 OP @levelworm 这个相似的题，我都是看到了。到现在我就不明白是在 怎么才能做到不重复。
|
|
36
EggtartZ 2020-06-12 12:40:56 +08:00
@hejw19970413 m 是每次最多走的台阶数，3 就是每次能走 1，2 或 3 格
|
|
37
hejw19970413 OP @EggtartZ 你这个好像是对的耶 ！厉害了 我的哥
|
 |
38
freemon 2020-06-12 12:49:23 +08:00 1
原题比较简单哈，变异之后用 dp 就好
定义 s[i][k] 为到达地 i 层阶梯且最后一步走 k 步的 走法数量 则 s[i][1] = s[i-1][2]+s[i-2][3] s[i][2] = s[i-2][1]+s[i-2][3] s[i][3] = s[i-3][1]+s[i-3][2] 确定一下初始值，然后计算 result = s[n][1]+s[n][2]+s[n][3] 即可 ？ |
|
39
buhi 2020-06-12 12:50:27 +08:00
f(n) = f(n-1) + f(n-2) + f(n-3), 求 f(n), 这个存在 O(1)的解法.
https://www.fq.math.ca/Scanned/20-2/spickerman.pdf (就是浮点数计算的话, 台阶数高了之后就误差很大了) |
|
40
hejw19970413 OP @buhi 哥你这个我有点晕
|
|
41
hejw19970413 OP @freemon 好 我理解下
|
|
42
Vegetable 2020-06-12 13:02:41 +08:00
@hejw19970413 #29 我那个思路减错啦
|
 |
43
lylsh1993 2020-06-12 13:33:02 +08:00 via iPhone
#30 楼 正解
|
 |
44
doudou1523102 2020-06-12 18:16:22 +08:00
关键字 “多少种” 这种要用动态规划区想了
|
 |
45
pangleon 2020-06-12 19:39:12 +08:00
这道题好做就是怎么能不报错，用迭代加备忘录一样会 stackoverflow
|
 |
46
BBCCBB 2020-06-12 19:45:30 +08:00
兄弟, 斐波数列
你百度一下一堆. 比在 v 站问高效啊. |
|
47
BBCCBB 2020-06-12 19:47:29 +08:00
而且这种 leetcode 的题一搜也是一堆思路解析. 多刷刷,多理解你就有感觉了
|
 |
48
octobered 2020-06-12 21:04:45 +08:00
面经题熟脸了.... 今年最少被问了三次这道题了 斐波那契完事
|
 |
49
nznd 2020-06-13 01:35:09 +08:00
```python
if n==1: return 1 first,second=1,2 for _ in range(3,n+1): first,second=second,first+second return second ``` 一个 空间 o(1) 时间 o(n)的解法(简单易懂 |
 |
50
ericgui 2020-06-22 01:28:30 +08:00
https://www.bilibili.com/video/BV1G54y1X72H
这是我讲的爬楼梯 70 题 其实变形就是 dp[k] = dp[k-1] + dp[k-2] + dp[k-3] 思路是一样的思路 |
|
51
hejw19970413 OP @ericgui 您成功的耽误了我 10 分钟。
|
|
52
ericgui 2020-06-24 00:37:58 +08:00
@hejw19970413 讲的不好？耽误您时间了，不好意思
|
|
53
hejw19970413 OP @ericgui 不是您讲的不好，只不过你说的和我题，完全不是一个概念，是都是用斐波那契数列 ， 你只要说我这个道变形题的痛点，和怎么考虑就好了。不同的斐波那契数列，可以玩成不同的解决办法。 您就比如说 变形题中的 上的台阶不相同 怎么考虑 ， 1 或 2 或 3 个台阶 怎么考虑 ？ 如果我要是 说 用斐波那契数列 就知道了怎么解决，就不会来问了 。
|
|
54
hejw19970413 OP @ericgui 也就可以打一个比方，我想吃饭，问西红柿炒鸡蛋怎么做，你说去买西红柿和鸡蛋 然后 加热 就 OK 了，您所说的是对的，也非常的好，但是不能解决我的问题。 大佬
|
|
55
hejw19970413 OP 这里的每一条回复我都去做了验证。。 包括所说的公式什么的，第 23 层我认为是正确的，第 30 层的得出来的结果有些偏差，普通的公式得出来的结果，只是适用为 前两个数之和。
|
|
56
ericgui 2020-06-24 10:11:17 +08:00
@hejw19970413 不好意思哈
|
Select Language