The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. ― Donald E. Knuth

# Algorithms

## Dynamic Programming

Problem :-
Longest Common Subsequence ( LCS ) problem.
Given two sequences, find the longest common subsequence present in both the sequences.
In subsequence, elements of the sequence need not be consecutive.
For e.g, "lgtm" is a subsequence of "algorithms".
Consider two sequences { 1, 2, 3, 2, 4, 1, 2 } & { 2, 4, 3, 1, 2, 1 }
Longest Common Subsequence ( LCS ) is { 2, 3, 2, 1 } of length 4.

Solution :-
Suppose we want to find LCS of two strings ( str1 of size m and str2 of size n )
First, we will characterize the structure of an optimal solution.
Let lcs ( i , j ) denotes the length of LCS till index i of str1 and index j of str2.
There are 2 possibilities :
1 ) if str1 ( i ) == str2 ( j ) , then the problem reduces to finding 1 + lcs ( i - 1 , j - 1 )
2 ) if str1 ( i ) != str2 ( j ) , then the problem reduces to finding maximum of the two overlapping subproblems
[ lcs ( i - 1 , j ) and lcs ( i , j - 1 ) ]
Thus, optimal solution is defined recursively as :
lcs ( i , j ) = 1 + lcs ( i - 1 , j - 1 ) if str1 ( i ) == str2 ( j )
lcs ( i , j ) = max [ lcs ( i - 1 , j ) , lcs ( i , j - 1 ) ] if str1 ( i ) != str2 ( j )
Now, lcs ( i , j ) can be found for any values of i and j.
Eventually, lcs ( m , n ) gives the required solution.
The implementation shown below maintains some additional information to print the actual Longest Common Subsequence apart from the length of LCS.