Binary_ToothLess's blog

Coin Change(Dynamic Programming)
By Binary_ToothLess, 10 years ago, In English

I just write here a structure for coin change problem:

433A — Kitahara Haruki's Gift

http://mirror.codeforces.com/problemset/problem/433/A

int recursion(int index, int amount){//initially index is 0, amount = amount of destination money

if(i >= total_types_of_Coin){//e.g:1c,5,10c = 3 types of coin here..

if(amount == 0)return 1;// base case

else return 0;

}

int way1 = 0, way2 = 0;

if(dp[index][amount] != -3)dp[index][amount];//dp was memset by the value of -3 in main function

if(amount-Coin[index] >= 0)way1 = recursion(index, amount-Coin[index]);//if we get same coin for several times otherwise index will be (index+1) that means try next coins;

way2 = recursion(index+1, amount);

return dp[index][amount] = way1+way2;

}

try it...i think this will work for following problems... UVa — 357, 674, 11137, 562;

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In algorithmic programming, we don't "think" sir rather we rigorously prove our claim.

The coin change problem can be formulated as

Let f(i,j) be the Number of ways to make change for value i using change from set S[1..j]

case 1 : S[j] > i

f(i,j) = f(i,j-1)

case 2 : S[j] <= i

f(i,j) = f(i,j-1) + f(i-S[j], j) //

base cases f(i,0)=0 f(0,j)=1 //only one way to solve if value to get is 0.

so using dp[n][m], we can build table in bottom-up fashion and solve the problem.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    "In algorithmic programming, we don't "think" sir rather we rigorously prove our claim".

    I disagree. I often begin coding right after words "I think this will work" appear in my head. There is little time for proofs in the contests, unless you actually need them to convince yourself (which might not even be necessary for contests with full feedback). How accurate are one's guesses heavily depends on the amount of practice one has though.

    → Reply