动态规划的找零算法 [英] Coin Change Algorithm with Dynamic Programming

问题描述

我在动态编程方面遇到困难。我正在尝试更改硬币的小问题-硬币更改问题UVa

I am facing difficulty with Dynamic Programming. I was trying the trivial Coin Change problem- COIN CHANGE Problem UVa

我正在尝试使用自上而下的方法进行记忆，但我遇到了TLE。这是我的代码-

I am trying to use top-down approach with memorization but I am getting TLE. Here is my 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;
    }
}

我想知道我记错了吗？ -down在这种情况下将不起作用，并且自下而上的方法是唯一的选择。

I want to know am I doing memorization wrong or top-down will not work in this case and bottom-up approach is the only option.

推荐答案

您不必致电Coin每个测试用例（每个n的值）的函数在所有情况下都保持不变（m（硬币的类型数）），因此对于最大值（此处为7489）仅调用一次。然后以dp [n] [4]的形式回答所有测试用例。请参阅下面的代码以更好地理解。

You do have not to call Coin function for every testcase(each value of n) as m(number of types of coins) remains same in all cases so call it only once for maximum value which is 7489 here. and then answer for all testcase as dp[n][4]. Please see the code below for better understanding.

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

这篇关于动态规划的找零算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！