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.
LightOJ 1057 - Collecting Gold
Category: This problem is a dynamic programming problem. Particularly this problem can be solved by bitmask dynamic programming technique.This problem can also be solved by using breath first search.
Techniques: When I have solved this problem then I was tried it by recursive dynamic programming technique. Your sample test cases may pass by these techniques but in case of mine I have defeat my code by a critical test case of mine. Then I thought it from different angle and I have solved it by the technique of bit-mask dynamic programming.
It is little hard to model the problem in bitmasking. If you don't have any idea about bit-masking then please learn it from internet. There are available resources. I did the same.
In the problem it has been told that the problem could have at best 15 gold. When the input size of a DP problem is less than 16 then this problem could be a bit-mask DP.
The gold has 15 pieces and a initial location(x) together makes 16. I think now you have got the clue.
At first please keep the locations of all gold pieces in a separate array of two dimension by index starting from 1. Now, use the zero index to store the location of initial position.
Now, calculate the distance of every gold pieces to each other including the initial position.
Suppose, Array to store locations is 'a' and array to store the distances is 'b'. My code was:
repc(i,0,m-1)
repc(j,0,n-1)
{
if(s[i][j]=='x'){ a[0][1]=i;a[0][2]=j;}
else if(s[i][j]=='g') {a[++c][1]=i;a[c][2]=j;}
}
repc(i,0,c)
repc(j,i+1,c)
{
b[i][j]=b[j][i]=max(abs(a[i][1]-a[j][1]),abs(a[i][2]-a[j] [2]));
}
I am not describing the code. You can try if you are willing to do so. The following part is interesting in code: "max(abs(a[i][1]-a[j][1]),abs(a[i][2]-a[j][2]))"
Isn't it?
This is the distance from one coordinate to another coordinate if you can move in all 8 direction. For four direction this equation could be failed!!
Please put two coordinates in your paper and try to figure out what's going on in this equation.
Now, everything is ready. You can start bit-masking procedure recursively. The memory you can use is at best 16*2^16.
If you have learn the bit-mask DP technique already then it shouldn't be a problem for you at all. If you don't then comment for further help. I shall try in shaa Allah.
Test Cases:
Input: 3
3 4
x..g
...g
g.gg
3 4
x..g
...g
gggg
20 20
....................
....................
.g...g..............
.............g......
....................
....g...............
..........g.........
g...................
.........x....g.....
....................
....................
...g................
....................
.....g......g.......
....................
..g.................
...........g...g....
....................
....................
g..................g
Output:
10
10
71
Techniques of LightOJ 1013 - Love Calculator
Category: This problem is mainly a Longest Common Subsequence Problem.
Techniques: If you read carefully the problem statements then you should already know that this problem can be solved in two parts.
In the first part what you need is to find the "The
length of the shortest string that contains the names as subsequence" and in the second part what you need is that "Total
number of unique shortest strings which contain the names as subsequence.". We are doing these in two parts too.
First Part: Here, we are going to find the
length of the shortest string that contains the names as subsequence. We can do this job in two ways as below.
- A way could be to find the longest common subsequence of the two given string and subtract it from the addition of the length of two given string.
How does it work?
We have to find the length of shortest string. So, We actually don't need to take a letter twice which is available in both the given string.
Suppose, A=bac and B=mct. The the resultant shortest subsequence will be C=bamct.
How? Answer: Since ba and c are not common at all so we have to take them all. now, next character c is common.Hence we can only take one. And at last t can be taken as the last character.
I think you know how to find the lcs of two string. If don't then learn it.
- Another way two find the 1st part could be a modified version of
longest common subsequence. In this process you don't need to subtract anything rather you do all the job in procedure lcs(). What you need here extra is that in the base case of recursive call, if any of the string got empty then you take the remaining letters in count.
Second Part:
The first part of this problem is relatively easy. But the second part is a little bit thinking.
Since you know the length of the shortest string from first part, it is very helpful and necessary here.
The function I have defined to do the work has three parameters. First is the present index of first string, second is the present index of second string and third is the number of characters we have taken till now.
Case are:
If the two characters are same then proceed to the next characters by unique(i+1,j+1,num+1).
If two characters are not same then proceed by calling like follow:
ret=unique(i+1,j,num+1)+unique(i,j+1,num+1).
The base case is more important in my technique:
If any of the string got finished then what you will do?
My answer is, in common you add all the remaining letters from given strings with the num value from paremeter. If it is equal to length from first part then return 1(right approach:) ) else return 0(wrong approach :().
Comment if you have any Question.
