algorithm - 动态规划的硬币找零算法

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

您不必为每个测试用例(n 的每个值)调用 Coin 函数，因为 m(硬币类型的数量)在所有情况下都保持不变，因此只需调用一次以获得最大值，此处为 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;   
}