I was recently solving Aibophobia on the popular algorithm problem online judge, SPOJ.
The problemâ€™s solution involves finding the Longest Common Subsequence of two strings.
A trivial solution to the problem is exponential in complexity. However, Dynamic Programming can be used to reduce the problem to time complexity $O(N^2)$.
There are usually two approaches to coding a Dynamic Programming solution. The first, is my favorite and very intuitive approach of Recursion with Memoisation, also known as the Topdown approach.
1 2 3 4 5 6 7 8 9 10 11 12 13 

Note that, here n, m are lengths of strings a and b, respectively and the dp array is initialized to 1. lcs(i,j)
gives the value of the Longest Common Subsequence of strings a and b, starting from the ith index of a and jth index of b. Note that in lines 911 implement how the answer will be calculated recursively, and 67 define when the recursion will be terminated. Why is this fast? Because we memoize the calculated values in the dp array and if lcs(i,j)
is called again, the cached value would be returned. The LCS of two strings would be returned by the call lcs(0,0)
.
Another approach is the bottomup approach, which is easy to understand once you code the topdown approach. The problem with the previous topdown approach is that, in cases of large inputs, recursive calls, despite memoisation, might cause the solution to have a big constant. The bottomup approach has the same $O(N^2)$ time complexity, but a lower constant.
My bottomup approach to the problem was as follows:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 

Note, the same problem is now done in the reverse fashion. The dp array needs to be initialized to be 0
only for all values of dp[n][0]
, and dp[0][m]
.
However, there is one small optimization that can be done here. We do not need a 2D array for dp, since for dp[i][j]
, it only needs the values of the dp[i+1]
row, other rows are redundant.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

The above solution reduces the problem to space complexity of $O(N)$. In practice, reducing the space complexity improves the actual running time, since the small array fits more easily in the cache.
Please refer the Dynamic Programming tutorial on TopCoder to learn more.