将“n”个物体分布在“n”个盒子中，使得没有盒子包含超过3个或“k”个物体

Question

帮助解决以下问题。

斐波那契是意大利比萨市的一位年轻居民。他花了很多时间参观比萨斜塔，这是该市的标志性建筑之一，距离他家很近。在他参观塔的所有过程中，他在爬塔的大理石台阶时都会玩一种奇怪的游戏。

游戏：斐波那契喜欢爬一级台阶，一次爬两个台阶，或者一次爬三个台阶。这为原本单调的攀登任务增添了多样性。他想要找到他可以爬上 n 个台阶的总方式，假设他的各个台阶的顺序很重要。你的任务是帮助斐波那契计算这个数字。

例如，如果他想爬三级台阶，在n=3的情况下，他可以用四种不同的方式来完成： (1,1,1)：分三步，一步一步 (1,2)：分两步进行，先单步，然后双步 (2,1)：分两步，先走两步，再走单步 (3)：一招搞定，直接跳到第三步 再举个例子，如果n=5，那么一些序列可能是： (1,3,1),(1,1,3),(3,1,1),(2,1,1,1),(1,2,1,1),(2,1,2 ） 每个序列都是攀爬五级台阶的方法之一。

这里需要注意的一点是，序列的每个元素只能是1、2或3。 编写一个名为steps的递归函数，它接受正整数n作为参数。它应该返回斐波那契上升 n 步的方式总数。请注意，他的步骤顺序很重要。

我假设逻辑与简单的组合问题相同，其中我们将“n”个不可区分的对象分配到“n”个可区分的盒子中，这样每个盒子最多包含“k”个对象，并找到每个对象的可能排列数量组合，因此得名。

Answer 1

这是一个 Tribonacci 序列，遵循序列 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)
}

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

注意：一种更有效的内存方法是不将其实现为递归函数，而是迭代地实现。