如何使用动态规划来优化这个cod

Question

多拉特·拉姆是个富有的商人。在非军事化之后，在他的住所进行了突袭，他的所有钱都被没收了。他非常渴望拿回自己的钱，他开始投资某些企业，并从中获利。第一天，他的收入是卢比X，第二天是卢比Y。道拉特拉姆观察到他的增长作为一个函数，并想计算他的收入在第n天。在

他发现的函数是FN=FN-1+FN-2+FN-1×FN-2

考虑到他在第0天和第1天的收入，计算他在第n天的收入（是的，就这么简单）。在

输入：

第一行输入由表示测试用例数的单个整数T组成。在

接下来的每一条T行分别由三个整数F0、F1和N组成。在

输出：

对于每个测试用例，打印一个单一的整数FN，由于输出可以很大，计算出答案模109+7。在

限制条件：

1≤T≤105

0≤F0，F1，N≤109

def function(x1):

 if x1==2:  return fnc__1+fnc__0*fnc__1+fnc__0
 elif x1==1: return fnc__1
 elif x1==0: return fnc__0

 return function(x1-1)+function(x1-2)*function(x1-1)+function(x1-2)


for i in range(int(input())):  #input() is the no of test cases
 rwINput = input().split()

 fnc__0 =int(rwINput[0])
 fnc__1 = int(rwINput[1])

 print(function(int(rwINput[2])))

Answer 1

您可以开始执行该函数并将f1分配给f0，并将结果赋给f1。重复此n次，得到的结果是f0：

MOD = 10**9 + 7

for _ in range(int(input())):
    f0, f1, n = (int(x) for x in input().split())
    for _ in range(n):
        f0, f1 = f1, (f0 + f1 + f0 * f1) % MOD

    print(f0)

输入：

^{pr2}$

输出：

1
2
5
17
107
1943
209951
276644752

Answer 2

有人给了我这个答案，但我不知道怎么做？复杂性O（logn）

#include <stdio.h>
#include <stdlib.h>
#define mod 1000000007
long long int power(long long int,long long int);
void mult(long long int[2][2],long long int[2][2]);
int main()
{
    int test;
    scanf("%d",&test);
    while(test--)
    {
        int n;
    int pp,p;
    scanf("%d%d%d",&pp,&p,&n);
    long long int A[2][2] = {{1,1},{1,0}};
    n = n-1;
    long long int B[2][2] = {{1,0},{0,1}};
    while(n>0)
    {
        if(n%2==1)
            mult(B,A);
        n = n/2;
        mult(A,A);
    }
   long long int result = ((power(pp+1,B[0][1])*power(p+1,B[0][0]))%mod - 1 + mod)%mod;
   printf("%lld\n",result);
   }



}

long long int power(long long int a,long long int b)
{
    long long int result = 1;
    while(b>0)
    {
        if(b%2==1)
            result = (result*a)%mod;
        a = (a*a)%mod;
        b = b/2;
    }
    return result;

}
void mult(long long int A[2][2],long long int B[2][2])
{
    long long int C[2][2];
    C[0][0] = A[0][0]*B[0][0] + A[0][1]*B[1][0];
    C[0][1] = A[0][0]*B[0][1] + A[0][1]*B[1][1];
    C[1][0] = A[1][0]*B[0][0] + A[1][1]*B[1][0];
    C[1][1] = A[1][0]*B[0][1] + A[1][1]*B[1][1];
    A[0][0] = C[0][0]%(mod-1);
    A[0][1] = C[0][1]%(mod-1);
    A[1][0] = C[1][0]%(mod-1);
    A[1][1] = C[1][1]%(mod-1);
}

Answer 3

一个简单的优化方法是缓存函数的结果。python提供了一种只使用hat的^{}机制。您只需使用以下内容来装饰您的功能：

from functools import lru_cache

@lru_cache()
def function(n, F0=1, F1=2):

    if n == 0:
        return F0
    elif n == 1:
        return F1
    else:
        f1 = function(n-1, F0, F1)
        f2 = function(n-2, F0, F1)
        return f1+f2 + f1*f2

您可以根据您的需要稍微调整一下lru_cache。它与python垃圾回收器配合得非常好，因为它只将WeakRefs存储到对象中。在

测试用例：

^{pr2}$

印刷品：

0:       1
1:       2
2:       5
3:      17
4:     107
5:    1943
6:  209951

要得到整数模的答案（问题中的模不清楚），可以执行以下操作：

^{4}$