我想问一道 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 题目