このコードを最適化するために動的プログラミングを使用する方法

Question

Daulat Ramは豊富なビジネスマンです。 demonetizationの後、彼のすべてのお金が押収された彼の宿泊施設でIT襲撃が開催されました。彼は彼のお金を取り戻すことを非常に熱望しています。彼は特定のベンチャーに投資し、彼らから儲け始めました。最初の日、彼の収入はRsでした。 X、続いてRs。 2日目のY。 Daulat Ramは彼の成長を関数として観察し、N日目に収入を計算したかった。彼が見つけた

機能は、FN = FN-1 + FN-2 + FN-1×FN-2

は0日と1日目に彼の収入を与えられた、ええ（N番目の日に彼の収入を計算しますそれは簡単です）。

INPUT：

入力の最初の行は、テストケースの数を表す単一の整数Tから成ります。

次のT行は、それぞれ3つの整数F0、F1、Nで構成されています。

OUTPUT：

各テストケースについて

は、単一の整数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

誰かが私にこの答えを与え、それが働いていたが、私ドンどのように知っている？複雑さ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 2

最適化する簡単な方法は、あなたの関数の結果をキャッシュすることです。 Pythonは、ちょうどその帽子のためのメカニズムをlru_cacheで提供します。

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ビットを微調整することができます：あなたがする必要があるすべては、これであなたの関数を飾るです。あなたのオブジェクトにのみWeakRefsを保存するので、pythonガベージコレクタでとてもうまくいきます。

テストケース：

for i in range(7): 
    print('{}: {:7d}'.format(i, function(i))) 

プリント：

MOD = 10**9 + 7 # ??? 

@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) % MOD 

：

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

あなたの答えを得るためには、あなたがこれを行うことができます（あなたの質問弾性率については明らかではない）整数を法

Answer 3

関数の実行を開始して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) 

入力：

出力

8 
1 2 0 
1 2 1 
1 2 2 
1 2 3 
1 2 4 
1 2 5 
1 2 6 
10 13 100 

：

1 
2 
5 
17 
107 
1943 
209951 
276644752