Computer Science @USC
Dynamic Programming tutorial on TopCoder is very good. I got started with solving some problems listed as exercises in the article. I think dynamic programming can be learnt only by practicing a lot. Here are my solutions for some of the problems listed. Longest Increasing sub sequence is a good place to start learning DP. I have explained the logic in the form of comments.
Given an array, find the length of the longest monotonically increasing sub sequence.
For example: Given 1, 4, 2, 3 -> the answer is 3 because of the sequence 1, 2, 3.
A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.
For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.
Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.
The old song declares "Go ahead and hate your neighbor", and the residents of Onetinville have taken those words to heart. Every resident hates his next-door neighbors on both sides. Nobody is willing to live farther away from the town's well than his neighbors, so the town has been arranged in a big circle around the well. Unfortunately, the town's well is in disrepair and needs to be restored. You have been hired to collect donations for the Save Our Well fund.
Each of the town's residents is willing to donate a certain amount, as specified in the int[] donations, which is listed in clockwise order around the well. However, nobody is willing to contribute to a fund to which his neighbor has also contributed. Next-door neighbors are always listed consecutively in donations, except that the first and last entries in donations are also for next-door neighbors. You must calculate and return the maximum amount of donations that can be collected.
Krishna, what happens if two numbers in the middle of the data are equal ? if sign is 0, you say we can choose any ... which is not true then
Anirban, it is indeed wrong. Cases like {20,20} or {4,4,4,3,3,3,5,5,5} as mentioned by Piyush below also will fail. I'll post a fix to when time permits.
Hope you are doing good!
In Zigzag the code fails for inputs like {20,20} or {4,4,4,3,3,3,5,5,5}
This kind of programming might still be new for someone who are still studying in programming. This will be a great help and a great opportunity for them which will surely guide them in many different ways that they need. It's the best thing that you have shared this one.
What is being done in the last if(i_included[N-1] && zero_included[N-1]) statement?? I know its being done because first and last elements can not be taken together but how are they doing it??
Thanks Krishna!
But is the Bad_Neighbors right with this case: { 11, 15 }? Should return 15? Not 0.
I suggest an improvement:
if we would print the index of the "good neighbors" that give money? = )
This solution to Bad Neighbors seems not correct.
The tricky part is how you define the dp[] array.
The two array solution means the precise definition of dp[i] is max sum INCLUDE i-th donation. So that the dp[n-2] MUST include neighbor n-2, and it can be calculated from dp[0] and ignore dp[n-1], you can ignore dp[n-1] because dp[n-1] must include neighbor n-1.
so if we make clean the definition of the dp[] array, the recursive is not
dp[i] = max(dp[i-2] + donations[i], dp[i-1]); (Here dp[i] is defined as max up to i, but i is not mandatory included)
correct recursive is :
dp[i] = max(dp[i-3], dp[i-2]) + donations[i] .
For more information, check the discuss on topcoder forum.
Sheng W, you are right. I have updated the code. It's not making use of the same exact recurrence relation that you have mentioned. It's slightly different. Take a look at it and let me know if you find any other problems with it :-)
Hi Sheng,
Why would you say max(dp[i-2] + donations[i], dp[i-1]) is not clean?
Correct me if I'm mistaken. I implemented BadNeighbors with Java and I get a wrong answer with 10, 3, 2,5, 1. Should be 15 but outputs 12.
kriegerd, I am sorry for such a late response. You were correct, there was a bug in my code. You can take a look at it now and it should be fixed.
Hi
your solution is not working for given value
{90, 1, 2, 89, 3, 4, 88, 5, 6, 87, 5, 4, 86, 3, 2, 85}
ans = 442
but it is returning = 436
because after this, you need to take max of all the zigzag sequences ending at all positions.. and return that
nice blog...keep going :)
Thanks for the solutions mentioned in this blog
Hi Krishna, Can you please explain your solution for bad neighbors. I am not sure why the two arrays are used. Also, why are u not setting the dp[1] in the first case and dp[0] in the second case.
Because you can select the donation only from one out of those two.
In the first case, dp[0] is set which means the donation from the first neighbor is accepted and with that we proceed ahead to find the max donation possible. Also notice that since 0th value of donation is accepted, we take the final answer from dp[N-2] which is the second to last neighbor (remember the neighbor's condition? A neighbor will only donate if their next and previous neighbors haven't donated.)
Similarly, in the next case, we start with dp[1] and move on ahead to find the max donation possible. In this case, since we have not considered the 0th neighbor, we can consider the donation made by the last neighbor - which is dp[N-1] - into the calculation.
Finally, since we have considered both the cases, we simply find the max value from among the two previously calculated max values and return the result.
Cheers! :)
Hi ,Pratik Joshi ,
The solution to Bad Neighbors seems not correct.
The tricky part is how you define the dp[] array.
The two array solution means the precise definition of dp[i] is max sum INCLUDE i-th donation. So that the dp[n-2] MUST include neighbor n-2, and it can be calculated from dp[0] and ignore dp[n-1], you can ignore dp[n-1] because dp[n-1] must include neighbor n-1.
so if we make clean the definition of the dp[] array, the recursive is not
dp[i] = max(dp[i-2] + donations[i], dp[i-1]); (Here dp[i] is defined as max up to i, but i is not mandatory included)
correct recursive is :
dp[i] = max(dp[i-3], dp[i-2]) + donations[i] .
For more information, check the discuss on topcoder forum here :