Co-founder @ SMERGERS and WealthBox.in

## Dynamic Programming16-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.