Techniques for LightOJ 1233 - Coin Change (III)

1233 - Coin Change (III) Hints:

Category: Iterative Dynamic Programming

Techniques:

Hey!! I am suggesting you the procedure I've followed!! Hope, it helps!!

This problem can be solved in O(n*m) time. where n=number of coins, m=amount.

Suppose, I want to check the money between 1 to 6.
I have coins 2,3. 2 can be used for 2 times.

The moneys are 1,2,3,4,5,6,7,8,9.
Suppose I want to start with coin 2.
then I'll iterate through 2 to 9 to check which money I can make with this coin.
Initially, You set dp[0]=1.//base case.
 
So, for 2 ,
starting from i=2,
I can make 2 since dp[2-[present_coin]]==1, i.e, dp[0]=1.
then set dp[2]=present coin.//since number of coins are limited, u will need this to check.
now store 1 in an array since this is the 1st use of coin 2.
_cnt array will store how many times a particular coin has been used to make a amount.

so, dp[2]=2.
_cnt[2]=1.

now, for i=3,
I can't make 3 since dp[3-[present_coin]]==0,i.e, dp[1]=0 and I couldn't make 1.
then leave it.
dp[3]=0.
_cnt[2]=0.

for i=4,
I can make 4 since dp[4-present_coin]==2, i.e dp[2]=2.
Here is a matter, since dp[4-present_coin]==2 that means coin 2 has been made with a use of present coin. Since number of coins is limited so you have to check _cnt array to determine whether you can use present coin or you have already used max time.

since _cnt[2]=1 that means you have used present coin 1 time to make previous amount,2. and if you want to make 4 using present coin then you will used present coin for _cnt[2]+1=2 times.Since I can use coin 2 for max 2 times so, I can use present coin to make 4.
dp[4]=2.
_cnt[4]=_cnt[2]+1.//1 for using present coin another time.

Now, for i=5,
I can't make 5 since dp[5-[present_coin]]==0,i.e, dp[3]=0 and I couldn't make 5 using present coin since coin 3 has not been made yet;
then leave it.
dp[5]=0.
_cnt[5]=0.

For i=6,
I can make 6 since dp[6-present_coin]==2, i.e dp[4]=2.
Here is a matter, since dp[6-present_coin]==2 that means coin 4 has been made with a use of present coin. Since number of coins is limited so you have to check cnt array to determine whether you can use present coin or you have already used max time.
Since cnt[4]=4 that means you have used present coin 2 times to make previous amount,4. and if you want to make 6 using present coin then you will used present coin for _cnt[4]+1=3 times,which is not allowed.Since I can use coin 2 for max 2 times so, I can't use present coin to make 6.
dp[6]=0.
_cnt6]=0.

The last case, i=6, is very important to understand.




  

Dont forget to comment if you have any problem.