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

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)

所以我的第一个冲动是简单地使用递归：

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时，只有一个解，即空序列。这不仅在数学上是正确的，而且也是递归正确工作所必需的。

该代码做了三件事以使其运行快速：

它使用缓存来缓存结果（记忆化），就像您所做的那样。
它不存储完整的结果，而是首先应用模数，大大缩小了取值范围。
它预加载缓存，从 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))

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

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 毫秒。

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

How to better implement recurrence relations in code?

python

algorithm

optimization

recursion

mathematical-optimization