algorithm - 使用第 1、2 或 3 步计算到达第 n 级楼梯的总数，但第 3 步只能走一次

Question

对于任何给定的值 N，我们必须在使用 1,2 或 3 的步骤时找到到达顶部的方法的数量，但我们只能使用 3 个步骤一次。例如，如果 n=7那么可能的方法是

[1,1,1,1,1,1,1]

[1,1,1,1,1,2]

等等 但我们不能有 [3,3,1] 或 [1,3,3]

我已经设法解决了一般情况，而没有使用动态规划仅使用 3 一次的限制，因为它形成了一种斐波那契数列

 def countWays(n) : 
    res = [0] * (n + 1) 
    res[0] = 1
    res[1] = 1
    res[2] = 2

    for i in range(3, n + 1) : 
        res[i] = res[i - 1] + res[i - 2] + res[i - 3] 

    return res[n] 

我如何找出其余部分？

Answer 1

设 res0[n] 是达到 n 步的方法数不使用 3 步，并令 res1[n] 是使用 3 步后达到 n 步的方法数。

res0[i] 和 res1[i] 可以很容易地从以前的值中计算出来，其方式类似于您现有的代码。

这是一个非常常见的技术示例，通常称为“图形分层”。参见，例如:Shortest path in a maze with health loss