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

[hejw19970413]

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

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

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

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

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

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

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

[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 哥你这个我有点晕