将'n'个对象分布在'n'框中,这样任何框都不包含超过3个或'k'个对象

这是一个 Tribonacci sequence ,按顺序 A000073 ,跳过前两个零,因此从0开始,序列为1、1、2、4、7、13、24。。。等。

一个简单的递归函数看起来像这样:

function steps(n) {
    if (n < 2) return 1
    if (n == 2) return 2
    return steps(n-3) + steps(n-2) + steps(n-1)
}

如果真的实现为递归函数,你最好应用记忆化来确保它在线性时间内执行。

请注意,这种递归实现的空间复杂度为O()。一种更节省内存的方法是不将其实现为递归函数,而是迭代实现,其空间复杂度为O(1):

function steps(n) {
    a = 0
    b = 0
    c = 1
    while (n > 0) {
        d = a + b + c
        a = b
        b = c
        c = d
        n = n - 1
    }
    return c
}

这背后的逻辑

首先,在楼梯的故事中,让我们称之为 步 楼梯的一部分,以及 移动 你爬楼梯的动作(在英语中,“step”一词可以同时用于这两个词,但这会让人很困惑)。

在故事中,当你离顶部只有几步之遥(并且>2)时,你有三个下一步的选择:一步、两步或三步,以相同的幅度减少。如果对于这些选项中的每一个,你都知道有多少可能性可以继续达到顶峰,那么你可以把这三个数字加起来,得出当你离顶峰只有几步之遥时有多少可能性。

所以我们有这个递归关系,其中 表示当你距离顶部仅几步之遥时的可能性数量:

= _1. + _2. + _3.

剩下的就是确定何时计数较小:

₀ 1.
_1. 1.
_2. 2.

第一个, ₀ ,可能感觉不直观,但当你距离顶部0步时,你已经到达了顶部,不需要再移动了。然而,你 实现 目标,所以它算作1:显然有一种方法可以达到顶峰——什么都不做。

有了这些规范,递归函数自然会随之而来。