ダイナミックプログラミングによるコイン変更アルゴリズム

Question

ダイナミックプログラミングに問題があります。私は些細なコインチェンジ問題を試していました - COIN CHANGE Problem UVa

私は暗記でトップダウンアプローチを使用しようとしていますが、私はTLEを取得しています。ここで私は、私はこのケースとボトムアップのアプローチでは動作しません暗記間違っていたり、トップダウンをしています知ってほしい私のコード -

#include <bits/stdc++.h> 
using namespace std; 
#define ll long long 

typedef vector <int > vi; 
typedef vector <vi> vii; 
const int maxn = 10000007; 

int Set[maxn]; 
int Coin(int n,int m,vii & dp) 
{ 
    if(n==0) 
     return 1; 
    else if(n<0 || m<0) 
     return 0; 

    else if(dp[n][m]!=-1) 
     return dp[n][m]; 
    else 
    { 
     dp[n][m]=Coin(n-Set[m],m,dp)+Coin(n,m-1,dp); 

     return dp[n][m]; 
    } 
} 

int main() 
{ 
    int n,m=5; 
    Set[0]=50,Set[1]=25,Set[2]=10,Set[3]=5,Set[4]=1; 
    while(scanf("%d",&n)!=EOF) 
    {  
     vector <vector <int> > dp(n+1,vector<int> (m,-1)); 
     dp[0][0]=0; 
     cout << Coin(n,m-1,dp) << endl; 
    } 
} 

で唯一のオプションです。

Answer 1

あなたはmと、すべてのテストケース（各nの値）（コインの種類の数）のためのコインの機能を呼び出すために持っていないので、ここで7489で最大値のために一度だけ、それを呼び出すすべてのケースで同じままです。すべてのテストケースに対してdp [n] [4]と答えます。より良い理解のために、以下のコードをご覧ください。

n = 7489; 
vector <vector <int> > dp(n+1,vector<int> (m,-1)); 
dp[0][0]=0; 
Coin(n,m-1,dp); 
while(scanf("%d",&n)!=EOF) 
{  

    cout<<dp[n][4]<<endl; 
}