current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free.
up vote 4 down vote favorite

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

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

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.

share|improve this question

migrated from programmers.stackexchange.com 2 days ago

This question came from our site for professional programmers interested in conceptual questions about software development.
    
What exactly is the semantics of dp[i][j]; is it the number of possible ways to use coins of type j for a money value of i or is it something different? –  Codor 2 days ago
    
Yes it is the number of ways to use coins of type j for money value i –  Joker 2 days ago

1 Answer 1

up vote 2 down vote accepted

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;   
}
share|improve this answer
    
Great, I guess this actually solves the problem. I had been trying to optimize the main algo part but never thought that it would be tested for multiple test cases. –  maandoo 2 days ago
    
Thanks a lot. I thought there was some problem with my optimization. –  Joker 2 days ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.