I just write here a structure for coin change problem:
433A — Kitahara Haruki's Gift
http://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;
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
case 2 : S[j] <= i
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.
"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.