How to write the memoisation function for this recurrence for the coin change problem?

Revision en1, by vikalp14, 2018-08-09 20:08:44

change(rs) gives the coins required for remaining value

  1. change(0) = 0 // we need 0 coins to produce 0 cents
  2. change(< 0) = ∞ // in practice, we can return a large positive value
  3. change(value) = 1 + min(change(value — coinValue[i])) ∀ i ∈ [0..n-1]

I wrote this but its not working (gives a large integer value !) ~~~~~

define INT_MA 999999

int memo[1000],v[1000]; int coin(int rs) { if(rs == 0) return 0; if(rs<0) return INT_MA; if(memo[rs] != INT_MA) return memo[rs]; int &a = memo[rs]; for(int i=0;i<n;i++) { a=min(a,coin(rs-v[i])); } if(a!=INT_MA) a=a+1; return a; } int main() { int n,val; cin>>n>>val;

for(int i=0;i<n;i++) cin>>v[i];

memset(memo,INT_MA,sizeof memo); cout<<coin(val); } ~~~~~

Tags #dynamic-programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English vikalp14 2018-08-09 20:09:43 4
en2 English vikalp14 2018-08-09 20:09:15 4
en1 English vikalp14 2018-08-09 20:08:44 860 Initial revision (published)