使用第 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]

etc 但我们不能有 [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

我们先忽略这里的三个步骤。想象一下，我们只能使用第一步和第二步。那么这意味着对于给定的数字 n。我们知道我们可以用 n 步骤 1 （一个解决方案）或 n-2 来解决这个问题]步骤1和步骤2（n-1解）；或者 n-4 步骤 1 和两个步骤 2，其中有 n-2×n-3/2个解，以此类推

方法的数量与斐波那契数列有关。很明显，构造 0 的方法只有一种：只是空列表 []。更清楚的是，构造1的方法也是一种：列表[1]。现在我们可以证明W_n构造n的路数是路数之和W_n-1构造n-1加上路数W _n-2构造n-2。证明是可以在每一种方式的末尾加1构造n-1，在末尾加2构造n-2。没有其他选择，否则我们会引入重复项。

方式数W_n因此与斐波那契数F_相同n+1 个 n+1。因此，我们可以实现带有缓存的斐波那契函数，例如：

cache = [0, 1, 1, 2]
def fib(n):
    for i in range(len(cache), n+1):
        cache.append(cache[i-2] + cache[i-1])
    return cache[n]

那么现在我们如何针对给定的三步解决此问题？我们这里可以采用分而治之的方法。我们知道，如果我们使用步长三，就意味着我们有：

1 2 1 … 1 2 3 2 1 2 2 1 2 … 1
\____ ____/   \_______ _____/
     v                v
  sum is <i>m</i>    sum is <i>n-m-3</i>

所以我们可以遍历m，每次乘以构造左边部分（fib(m+1)）和右边部分（[=19）的方法数=]) 我们这里可以使用 m 从 0 到 n-3 （包括两者）：

def count_ways(n):
    total = 0
    for m in range(0, n-2):
        total += fib(m+1) * fib(n-m-2)
    return total + fib(n+1)

或更紧凑：

def count_ways(n):
    return fib(n+1) + sum(fib(m+1) * fib(n-m-2) for m in range(0, n-2))

这给了我们：

>>> count_ways(0)  # ()
1
>>> count_ways(1)  # (1)
1
>>> count_ways(2)  # (2) (1 1)
2
>>> count_ways(3)  # (3) (2 1) (1 2) (1 1 1)
4
>>> count_ways(4)  # (3 1) (1 3) (2 2) (2 1 1) (1 2 1) (1 1 2) (1 1 1 1)
7

Answer 2

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

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

这是一个非常常见的技术示例，通常称为 "graph layering"。参见，例如：Shortest path in a maze with health loss

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

Count the total number ways to reach the nth stair using step 1, 2 or 3 but the step 3 can be taken only once

algorithm

graph-layering