This should be a wiki, and if I forget as always to turn it into a wiki tell me as it is always good to have it as a wiki.
This time I am going for a problem that is best not solved with recursion, but dynamic programming. However, it is not an easy feat to do so and I hope somebody will be up tithe challenge.
It is another classic: LCS or also known as the longest common subsequence problem.
Given two strings, the longest common subsequence is the longest sequence of characters that appear in the same relative order in both strings, but not necessarily consecutively. For example, for the strings “ABCDGH” and “AEDFHR”, the longest common subsequence is “ADH” (A-D-H).
Let’s give it a try in a language of your choice with an approach of your choice and exploit any weird thing of that language. Recursion, dynamic programming, loops. Everything is allowed but dynamic programming is by far the best (and probably hardest) way to solve this.
As reference about dynamic programming: The complete beginners guide to dynamic programming - Stack Overflow Blog
