我想问一道 LeetCode 变形题：（70）爬楼梯（变形）

[hejw19970413]

原题： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

变形： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 或 3 个台阶，且每次上的台阶不相同。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

哥哥们 这个变形 怎么解答 ？ 怎么个思路 ？

[hejw19970413]

有没有大佬可以试着解决一下 ，弟弟想了一宿没思路

[hello2060]

很难吗？开一个数组 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] ? 什么叫每次上的台阶不同

[Vegetable]

什么叫每次上的台阶不同？还能有相同的？

[winterfell30]

斐波那契数列

[Vegetable]

有点读懂了，试说每次上的台阶数不能与上一步相同？这个也算变种吗？可以说这是变了个数吧

[VoidChen]

我想问下有没有好的刷 leecode 的总结。。之前在 github 看到一个按算法类型来分类的，我不知道保存到哪没了。。

[cheese]

@hello2060 #2
@Vegetable #3
应该的意思是，爬过 1 之后，下一次只能 2，3 。每次的选择台阶数，不能和上一次的数字相同

[leavan]

哦我懂了，就是其他方法走过一次的楼梯不能再走了呗。那不是很简单吗？从楼顶往回看，最多只有三个台阶可以一步到楼顶，那么我们只需要证明这三种方法都可行就行了，每次都往前各推三步（如果有一个不是三步的，那么势必会造成重复），发现推到边界处仍然不会重复，所以有三种方法。答案就是 3，当然如果你 n 只有 1 或 2 的话那么方法也相应减少。

[coderraven]

怎么有点二叉树的感觉
用过 1，那么左右子树就只能是 2 和 3 。
用过 2，那么左右子树就只能是 1 和 3.
用过 3….

最后再走一波数值和是 n 的遍历？

[leavan]

@leavan 无视我这条，看了大家的回复发现我理解题意了。

[zhjy23212]

dp 里面每个状态存之前到这个点的步数，下次遍历跳过这几个。

基本上是 frog jump 的变体

[hejw19970413]

@Vegetable 比如 上 2 阶 只可以一次性上 2 级 不能是 1 级 1 级

[EggtartZ]

`dp[n, 1] = dp[n - 3, 2] + dp[n - 4, 3]` 这样的意思？

[leavan]

如果是跟上一步的台阶不同的话，那就动态规划。
```
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]
```

[hello2060]

那就不要 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 的方法数

[hejw19970413]

@hello2060 大佬 你这个第三个不对啊。1+1+2 = 4 第三级 那有 4 种啊 3 ，12 ，21

[hello2060]

@hejw19970413 第三个我不是没算嘛 xx 反正就那个意思，哈哈

[Vegetable]

大概想了一下
可以重复的时候，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))
是这样吗

[hejw19970413]

@Vegetable 我去跑一下

[xw900812]

dynamic programming... YouTube 搜 huahua leetcode 讲这道爬楼梯的问题，很经典的 DP 题目

[buhi]

第一个题就是斐波那契数列, 答 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))
}

[MoYi123]

三个数字的斐波那契数列

[EggtartZ]

```
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])
```
大概是这样吧

[mymike]

这个和最近的刷房子类似 需要加一个维度

[larisboy]

数组+斐波那契数列

[hello2060]

@buhi 斐波那契就是 DP 啊，一个问题可以分解成类似的子问题，而且子问题的解有重复的地方。

[buhi]

算斐波那契是 O(1), dp 不是 O(1)

[hejw19970413]

@buhi 大佬。按照您的公式算出来 答案不对

[hejw19970413]

@Vegetable 我需要手动算到 6 还是 7 啊

[lxy42]

```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])
```

[hejw19970413]

@EggtartZ 您这个 m 是啥？

[hejw19970413]

@lxy42 大佬。您这个从 4 开始都是 3

[levelworm]

这个感觉和分硬币有点像，总共 X 美元，有 5 分，一毛，25 分，50 分以及一美元，求问总共有几种分法。SICP 上第一章有答案。

[levelworm]

我直接抄书，我认为这个分硬币和上楼梯是一个事情。

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.

[hejw19970413]

@levelworm 这个相似的题，我都是看到了。到现在我就不明白是在 怎么才能做到不重复。

[EggtartZ]

@hejw19970413 m 是每次最多走的台阶数，3 就是每次能走 1，2 或 3 格

[hejw19970413]

@EggtartZ 你这个好像是对的耶 ！厉害了 我的哥

[freemon]

原题比较简单哈，变异之后用 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] 即可 ？

[buhi]

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
(就是浮点数计算的话, 台阶数高了之后就误差很大了)

[hejw19970413]

@buhi 哥你这个我有点晕

[hejw19970413]

@freemon 好 我理解下

[Vegetable]

@hejw19970413 #29 我那个思路减错啦

[lylsh1993]

#30 楼 正解

[doudou1523102]

关键字 “多少种” 这种要用动态规划区想了

[pangleon]

这道题好做就是怎么能不报错，用迭代加备忘录一样会 stackoverflow

[BBCCBB]

兄弟, 斐波数列

你百度一下一堆. 比在 v 站问高效啊.

[BBCCBB]

而且这种 leetcode 的题一搜也是一堆思路解析. 多刷刷,多理解你就有感觉了

[octobered]

面经题熟脸了.... 今年最少被问了三次这道题了 斐波那契完事

[nznd]

```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)的解法(简单易懂

[ericgui]

https://www.bilibili.com/video/BV1G54y1X72H

这是我讲的爬楼梯 70 题

其实变形就是 dp[k] = dp[k-1] + dp[k-2] + dp[k-3]

思路是一样的思路

[hejw19970413]

@ericgui 您成功的耽误了我 10 分钟。

[ericgui]

@hejw19970413 讲的不好？耽误您时间了，不好意思

[hejw19970413]

@ericgui 不是您讲的不好，只不过你说的和我题，完全不是一个概念，是都是用斐波那契数列 ， 你只要说我这个道变形题的痛点，和怎么考虑就好了。不同的斐波那契数列，可以玩成不同的解决办法。 您就比如说 变形题中的 上的台阶不相同 怎么考虑 ， 1 或 2 或 3 个台阶 怎么考虑 ？ 如果我要是 说 用斐波那契数列 就知道了怎么解决，就不会来问了 。

[hejw19970413]

@ericgui 也就可以打一个比方，我想吃饭，问西红柿炒鸡蛋怎么做，你说去买西红柿和鸡蛋 然后 加热 就 OK 了，您所说的是对的，也非常的好，但是不能解决我的问题。 大佬

[hejw19970413]

这里的每一条回复我都去做了验证。。 包括所说的公式什么的，第 23 层我认为是正确的，第 30 层的得出来的结果有些偏差，普通的公式得出来的结果，只是适用为 前两个数之和。

[ericgui]

@hejw19970413 不好意思哈