从盒子中取出物品的方法数

Question

我遇到了以下算法问题，该问题对运行时间有严格的限制（<10s并且没有大的内存占用），我被难住了。我的方法一半的测试用例都失败了。

问题

一个盒子包含许多物品，一次只能取出 1 个或 3 个。

盒子可以有多少种方式被清空？答案可能非常大，因此将其返回为 10^9+7 的模。

例如，最初有n=7个项目。可以通过九种方式删除它们，如下所示：

1.(1,1,1,1,1,1,1)
2.(1.1.1.1.3)
3.(1,1,1,3,1)
4.(1,1,3,1,1)
5.(1,3,1,1,1)
6.(3,1,1,1,1)
7.(1,3,3)
8.(3,1,3)
9.(3,3,1)

所以该函数应该返回 9。

函数描述：您的函数必须接受一个参数，n表示项目的数量，并返回一个整数，表示清空盒子的方式数。

限制条件：1<=n<=10^8

案例示例：

Input: 1
Sample OutPut: 1
Explanation: There is only 1 way to remove 1 item. Answer=(1%1000000007)=1

Input: 7
Sample OutPut: 9
There is only 9 ways to remove 7 items

我的方法

这导致了一个标准的递归关系，其中f(n) = f(n-3) + f(n-1)n > 2，所以我这样做如下

def memoized_number_of_ways(dic, n):
    if n not in dic:
        dic[n] = memoized_number_of_ways(dic, n-3) + memoized_number_of_ways(dic, n-1)
    return dic[n]

def numberOfWays(n):
    # Write your code here
    memoize = {1:1,2:1,3:2}
    import math
    ans = memoized_number_of_ways(memoize,n)
    return ans % (math.pow(10,9) + 7)

然而，这在任何情况下都会失败n > 10**2。在内存不多的情况下，如何在10 秒n以内解决这个问题？10^8

Answer 1

只需使用矩阵编写递归即可（请原谅我编写矩阵的方式，StackOverflow 不允许 LaTeX）。

[f(n)  ] = [1 0 1] [f(n-1)  ]
[f(n-1)] = [1 0 0] [f(n-2)  ]
[f(n-2)] = [0 1 0] [f(n-3)  ]

现在您所要做的就是将一个 3x3 矩阵（模固定常数）进行 n 次方（或 n-3 或类似的东西，具体取决于您的“基本情况列向量”，填写详细信息），然后将其乘以“基本情况列向量”。这可以在 O(logn) 时间内完成。

PS：您可能想查找矩阵求幂。