python - 如何在代码中更好地实现递归关系？

Question

几天来我一直在为这个问题而苦苦挣扎，我对 Python 和更多数学密集型编码仍然是新手，所以任何帮助将不胜感激，只要指出正确的方向:)

所以问题是这样的:

You have a movie pass which is valid for N days. You can use it in any way you want except for 3 consecutive days or more.

So basically, you can either use your pass on a given day or choose to not, meaning 2 raised to N total possibilities. The valid ways for claiming the pass are then 2 raised to N - invalidCases

You have to find the number of valid cases % (10^9+7)

我发现无效案例的递归关系看起来像

invalidCases(at_N) = 2^(n-4) + 2*invalidCases(at_N-1) - invalidCases(at_n-4)

所以我的第一 react 是简单地使用递归:

def invalidCases(n):
    if(n<3):
        return 0;
    elif(n==3):
        return 1;
    else:
        return 2**(n-4)+ 2*invalidCases(n-1)- invalidCases(n-4)

效率很低，但我的等式似乎是正确的。我的下一次尝试，我尝试了内存，但我一直在 N=1006 处遇到错误。所以我改变了递归限制。

我目前的尝试(使用内存和增加递归限制)

import sys
sys.setrecursionlimit(10**6)
T=int(input());
#2**(n-4) + 2*ans(n-1)-ans(n-4)
memo={0:0,1:0,2:0,3:1,4:3,5:8,6:20,7:47} #
def ans(n):
    #complete this function
    if n not in memo:

        memo[n]=(2**(n-4) + 2*ans(n-1)-ans(n-4));



    return memo[n];

modulo = 10**9 + 7;
print((2**n-ans(n))%modulo);

最后，我的问题。我需要此代码才能为 n = 999999 工作。

如何将最坏的情况降到最低？任何指示或提示都会很棒。

Answer 1

这是一个完整的解决方案，它基于以下观察:三天或更长时间的有效解决方案必须从以下之一开始:

0
10
110

其中 1 表示当天使用了通行证，0 表示未使用。

第一种形式有有效的(n-1)种可能性，第二种形式有有效的(n-2)种可能性，第三种形式有有效的(n-3)种可能性。

那么递归就是:

valid(n) = valid(n-1) + valid(n-2) + valid(n-3)

基本情况是 valid(0) = 1、valid(1) = 2 和 valid(2) = 4。重要的是要注意 valid(0) 是 1，而不是零。这是因为当n=0时，只有一个解，即空序列。这不仅在数学上是正确的，而且也是递归正确工作所必需的。

这段代码做了三件事来让它运行得更快:

1. 它使用缓存来缓存结果(记忆化)，就像您所做的那样。
2. 它不存储完整的结果，而是先应用模数，大大缩小取值范围。
3. 它预加载缓存，从 0 开始，一直到所需的值。这会将最大递归深度减少到一。

代码如下:

cache = {}
modulus = 10**9 + 7

def valid(n):
    if n in cache:
        return cache[n]

    if n == 0:
        v = 1
    elif n == 1:
        v = 2
    elif n == 2:
        v = 4
    else:
        v = valid(n-1) + valid(n-2) + valid(n-3)

    v %= modulus

    cache[n] = v
    return v

def main():
    # Preload the cache
    for n in range(1000000):
        valid(n)

    print(valid(999999))

main()

这是输出:

746580045

它在我的系统上运行不到 2 秒。

更新:这是一个最小的迭代解决方案，灵感来自 MFisherKDX 使用的方法。种子值的构建方式消除了对特殊外壳的需求(初始 v2 有效(0)):

modulus = 10**9 + 7

def valid(n):
    v0, v1, v2 = 0, 1, 1

    for i in range(n):
        v0, v1, v2 = v1, v2, (v0 + v1 + v2) % modulus

    return v2

print(valid(999999))

此解决方案可能会尽可能快。它会在使用后丢弃中间结果，如果您只调用该函数一次，这很好。