Thuật toán thay đổi tiền xu với lập trình động

Question

Tôi đang gặp khó khăn với Lập trình động. Tôi đã thử vấn đề Coin Change tầm thường- COIN CHANGE Problem UVa

Tôi đang cố gắng sử dụng phương pháp tiếp cận từ trên xuống với ghi nhớ nhưng tôi nhận được TLE. Đây là mã của tôi-

#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; 
    } 
} 

Tôi muốn biết tôi ghi nhớ sai hoặc từ trên xuống sẽ không hoạt động trong trường hợp này và cách tiếp cận từ dưới lên là lựa chọn duy nhất.

Answer 1

Bạn không được gọi hàm Coin cho mỗi testcase (mỗi giá trị n) dưới dạng m (số loại tiền) vẫn giữ nguyên trong mọi trường hợp, chỉ gọi một lần với giá trị tối đa là 7489 tại đây. và sau đó trả lời cho tất cả các testcase dưới dạng dp [n] [4]. Vui lòng xem mã bên dưới để hiểu rõ hơn.

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; 
}