Recursion to Dynamic Programming

A Step by Step Approach to Solve Any Dynamic Programming Problem

Photo by veeterzy on Unsplash

There are a lot of articles explaining the concepts of Dynamic Programming and ways to solve a problem using the Top-Down and Bottom-Up Approach of Dynamic Programming. If you haven’t read I would suggest you have a read at my article which covers the basics of Dynamic Programming.

Not many people know that Recursion is the parent of the Dynamic Programming solution. One cannot solve a Dynamic Programming Solution unless he/she knows how to solve a recursive problem.

Finding the recursive relation is what derives a Dynamic Programming Solution. In this article, we are going to take an example problem from LeetCode called Longest Common Subsequence and then solve it through recursion then Top-Down Approach ( Memoization ) and then convert it into the Bottom-Up Approach.

Problem Statement:

Given two strings str1 and str2, return the length of their longest common subsequence.
Input: str1 = "abcde", str2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Recursive Solution:

There are two important elements of a Recursion Problem:

1. Finding the Base Case
2. Finding the Recurrence Relation

In the Longest Common Subsequence Problem, the base case or smallest possible solution is when any one of the string is empty.

if m == 0 or n == 0:
return 0;

The recurrence relation is simple to find. If the m and n values are equal then we add one and find the longest common subsequence of the rest of the string.

if str1[m-1] == str2[n-1]:
return 1 + lcs(str1, str2, m-1, n-1);
else:
return max(lcs(str1, str2, m, n-1), lcs(str1, str2, m-1, n))

But if they are not equal we have to call two function calls as shown above and take the max value as result.

Top-Down Approach ( Memoization ):

If we draw a recursive tree for the recursion solution we find that many function calls are repeatedly called. This is one of the properties of the Dynamic Programming Problem called overlapping subproblems.

This overlapping problem is solved through Memoization where once the result of a function call is processed we store the result in memory and when a function is called again with the same inputs we return the cached result.

In the above solution, the result is stored in a two-dimensional table called L.

Bottom-Up Approach:

In the Bottom-Up approach, we use an iterative approach to solve the Dynamic Programming problem from the bottom. We start by initializing the base cases in the table and use the previously computed results to move forward.

Create a two-dimensional table with the length of the strings as rows and columns

L = [[None]*(n+1) for i in range(m+1)]

Use two for loops and the approach is similar to recursion where we have two conditions when both characters are similar and when they aren’t

Time Complexity Analysis:

1. Recursive Solution: The recursive Solution in the worst case has an exponential time complexity of O(2^N).
2. Top-Down Approach ( Memoization ): The top-down approach solves the problem in O(mn) time where m is the length of String 1 and n is the length of String 2.
3. Bottom-Up Approach: It requires two loops and hence it has a time complexity of O(mn) similar to the Top-Down Approach.

Both the Top-Down and Bottom-Up Approach have same time complexity but Since the Top-Down Approach is implemented using recursion there is a chance of stack overflow due to excess of Recursive calls.

Thank you for reading the article till the end, hope this article will help you in your coding preparations. Do follow me for more such articles.

Resources:

Dynamic Programming Made Easy

Longest Common Subsequence - LeetCode

Longest Common Subsequence | DP-4 - GeeksforGeeks