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

• 主 資深大佬 : 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 正解

• 資深大佬 : yt1523102

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

• 資深大佬 : 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)的解法(简单易懂