Dynamic Programming : An example showing Lowest Common Subsequence in Java

Introduction

Optimal Substructure : A problem is said to be a optimal substructure if an optimal solution can be constructed from optimal solution of it’s subproblem.

Overlapping subproblems : A problem is said to have overlapping subproblems if the problem can be broken down into repetitive subproblems.

Greedy Algorithm is used to solve problems having optimal substructure. But if the same problem has overlapping subproblems, dynamic programming is used in such cases.

The Problem

Longest Common Subsequence : Let’s say, we have two strings  ABXC and ADYC.

Here, the longest common subsequence(lcs) is AC. But how? If you see the strings backward, you will realise that both have ‘C’ at the end. That effectively means that our longest common subsequence has ‘C’ at the end and now the problem has reduced to find the longest common subsequence of ABX and ADY.

ABX and ADY don’t have anything common at the end, so what should will be the lcs here. Either it will lcs of AB and ADY or it will be lcs of ABX and AD; depending upon which one is greater.

LCS of AB and ADY in turn depends on A and ADY or AB and AD. Similarly we could go on recursively to see following pair of substrings evaluated for lcs between them

Recursive pairs are : ABXC-ADYC
Recursive pairs are : ABX-ADY
Recursive pairs are : AB-ADY
Recursive pairs are : A-ADY
Recursive pairs are : -ADY
Recursive pairs are : A-AD
Recursive pairs are : -AD
Recursive pairs are : A-A
Recursive pairs are : –
Recursive pairs are : AB-AD
Recursive pairs are : A-AD
Recursive pairs are : AB-A
Recursive pairs are : A-A
Recursive pairs are : AB-
Recursive pairs are : ABX-AD
Recursive pairs are : AB-AD
Recursive pairs are : ABX-A
Recursive pairs are : AB-A
Recursive pairs are : ABX-

You will notice that this problem can be solved recursively. Here’s the code for that:

The output for this code is:

—————Longest Common Subsequence Using Recursive Method—————–
LCS is GTABD
Time Taken : 192 ms

However, if you notice the recursive pairs that I mentioned above, there are many pairs in duplicate whose computation we can avoid with little space. We can store the recursive pair and lcs for that in a hashmap and check that before going for the recursive approach. Here’s the code for that:

The output for this code is :

—————Longest Common Subsequence Using Recursive Method And Memoization—————–
LCS is GTABD
Time Taken : 1 ms

Did you notice the difference in time taken in both case? Memoization increased the speed by 190 times.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

Up ↑

%d bloggers like this: