This was used in my solving of SPOJ 11110. Easy Longest Increasing Subsequence ELIS and is in git and below:

Continue reading

# Tag Archives: dynamic-programming

# Red John is Back

You need to build a solid wall that’s 4-high and N-wide using 4×1 bricks. The question: how many distinct walls can you build?

If you place a brick vertically, that takes up one entire column. Placing 4 bricks horizontally takes up four. The solution makes use of the simple dynamic programming recursion shown below:

Without further ado, my DP implementation is in git and below:

Continue reading

# Palindrome

The question is: given a string, can you find the longest palindrome sub-sequence?

N.B. A sub-sequence of a string is what remains after removing any characters you’d like, keeping the order unchanged. Sub-sequences of are , , , , etc. The following are not: , , , .

The solution uses dynamic programming on a 2D vector, with input string along both the top and side. The number of cells is .

Grid[row][col] means “longest sub-sequence within input sub-string [col…row]”. The grid is calculated from top to bottom, each row from right to left.

Explanations:

N.B. LCPal is Longest Common Sub-Sequence Palindrome

1. LCPal of “” is “”

2. LCPal of “” is “”

3. LCPal of “” is “” (taken from row above)

4. LCPal of “” is “” (take the match plus row/column above/beside, which is empty)

5. LCPal of “” is “” (taken from column beside)

6. LCPal of “” is “” (taken from row above)

7. LCPal of “” is “” (take the match plus row/column above/beside), and that’s the final answer

And an implementation note: because each row only requires the previous, I don’t keep all rows in memory — just two.

My solution is in git and below:

Continue reading