如何使用动态规划来优化这个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

一个简单的优化方法是缓存函数的结果。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}$