he following is a dynamic programming implementation to find the longest increasing subsequence (Wikipedia
). It runs in time
This was used in my solving of SPOJ 11110. Easy Longest Increasing Subsequence ELIS and is in git and below:
his post is in reference to SPOJ 21525. Red John is Back PPBRJB
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:
his post is in reference to CodeForces 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.
Example input =
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: