Co-founder @ SMERGERS and

Dynamic Programming 16-Nov-2012

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.

Longest Increasing subseqence

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.

ZigZag Sequence

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.

Bad Neighbors

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.

blog comments powered by Disqus