Ich habe Schwierigkeiten mit der dynamischen Programmierung. Ich habe versucht, die triviale Münze ändern Problem- COIN CHANGE Problem UVaMünzwechselalgorithmus mit dynamischer Programmierung
Ich versuche, Top-down-Ansatz mit Auswendiglernen zu verwenden, aber ich bin immer TLE. Hier ist mein Code-
#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;
}
}
ich wissen will, bin ich Auswendig falsch oder top-down tun wird in diesem Fall und Bottom-up-Ansatz nicht funktioniert ist die einzige Option.
Was genau ist die Semantik von 'dp [i] [j]'; Ist es die Anzahl der Möglichkeiten, Münzen vom Typ 'j' für einen Geldwert von' i' zu verwenden oder ist es etwas anderes? – Codor
Ja, es ist die Anzahl der Möglichkeiten, Münzen vom Typ j für Geldwert zu verwenden i – Joker