如何更好地实现代码中的递归关系？

Question

我已经为这个问题挣扎了几天了，我还不熟悉Python和更多的数学密集型编码，所以任何帮助都会受到感谢，请给我指出正确的方向:)

所以问题是：

您有一张电影通行证，有效期为N days。除连续3天或更长时间外，您可以任意使用它。 因此，基本上，您可以在给定的一天使用您的传递，或者选择不使用，这意味着2被提升为N的全部可能性。获得通行证的有效方法是将2提高到N- invalidCases。 您必须找到有效案例数% (10^9+7)

我找到了一个关于无效病例的复发关系，看起来

invalidCases(at_N) = 2^(n-4) +2*失效案例(at_N-1)- invalidCases(at_n-4)

因此，我的第一个想法是简单地使用递归：

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表示当天使用pass，0表示不使用pass。

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

然后，这种情况再次发生：

有效(N)=有效(n-1)+有效(n-2)+有效(n-3)

基本情况是有效(0)= 1，有效(1)= 2，有效(2)= 4。重要的是要注意有效(0)是1，而不是零。这是因为当n=0时只有一种解决方案，即空序列。这不仅在数学上是正确的，而且也需要递归才能正确地工作。

代码做了三件事来使它运行得更快：

1. 它使用缓存来缓存结果(回忆录)，就像您之前所做的那样。
2. 它不存储全部结果，而是首先应用模数，大大缩小了数值范围。
3. 它预加载缓存，从0开始，然后上升到所需的值。这将最大递归深度降低到1。

下面是代码：

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))

这个解决方案可能是你所能得到的最快的。在使用它们之后，它会丢弃中间结果，如果只调用函数一次，这是很好的。

Answer 2

这是我的答案。自下而上的解决方案。与汤姆的答案相比，这个答案是自上而下的，同样有效。在每天的j中，它都会跟踪使用第一天j传递的可能性的数量，以及在j和j-1上使用传递的可能性的数量。

def ans(n):

    total = 1
    tcd = 0 #total used at current day
    tcpd = 0 #total used at current and previous day
    m = 1000000007

    for j in range(0, n):

        next_tot = 2*total - tcpd
        next_tcd = total - tcpd
        next_tcpd = tcd - tcpd

        total = next_tot % m

        tcd = next_tcd % m
        tcpd = next_tcpd % m

    return total

print(ans(999999))

结果是746580045，在我的系统上花费400毫秒。