Introduction to Dynamic Programming: Overlapping Subproblems & Optimal Substructure

Introduction

Let’s assume that we had a question to solve the square of 25. If we are facing this question for the first time, then we may solve it either on hand or using a calculator. But if we’ve already seen this question before or solved this before, then there’s a possibility that we may answer it quickly by memorizing it.

This brings us to the conclusion that, if we can remember it then we can skip it next time. Dynamic programming works on a similar concept, the idea is to remember the result of a computation and use it in the future if required.

This simple procedure of dynamic programming makes it a strong weapon for a programmer to conquer the battle of efficient code.

For example, let us assume that we have a complex question and we always think of a solution that divides the question into subproblems. But we may get stuck in a situation where we will compute a subproblem multiple times. There we use dynamic programming for an optimal solution.

Dynamic programming has two concepts:

  1. Overlapping subproblems
  2. Optimal substructure

Overlapping Subproblems

A classic example of understanding the overlapping subproblem concept is a program to print the Fibonacci series.

The logic of the Fibonacci series is given by “fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)”. And executing this function seamlessly can be done using a recursive solution, with a base case of fibonacci(0)=0 and fibonacci(1)=1.

public static int fibonacci(int n){
        if(n==0 || n==1)
            return n;
        return fibonacci(n-1)+fibonacci(n-2);
    }
public static void main(String[] args){
System.out.print(“4th fibonacci number is “+fibonacci(4));
}

Say we need to print the 4th fibonacci digit, then the recursion tree goes as

                                          fibonacci(4)

                                         /                  \

                       fibonacci(3)        +          fibonacci(2)

                       /                 \                    /                \

       fibonacci(2) + fibonacci(1)   fibonacci(1) + fibonacci(0)

              /        \

fibonacci(1) + fibonacci(0)

Note that fibonacci(4) is the 5th digit in the fibonacci series because we start from fibonacci(0). In the above recursion tree, we can see that fibonacci(2) is repeated twice. We have observed duplication in a recursion tree of height 4, now imagine we have a recursive call of a huge number, and subsequently, there will be a recursion tree with a big height. And there will be many such duplicate computations, which are known as overlapping subproblems.

We have two methods to deal with this (i)tabulation, (ii) memoization

Let us understand them by walking through their implementations.

Memoization

Solving the fibonacci problem using the memoization method can be done as shown below

static int[] memo;
public static int fibonacci(int n){
if(memo[n]!=-1)
return memo[n];
if(n==0 || n==1){
memo[n]=n;
return n;
}
memo[n] = fibonacci(n-1)+fibonacci(n-2);
return memo[n];
}
public static void main(String[] args){
memo=new int[5];
for(int i=0;i<=4;i++)
memo[i]=-1;
System.out.println(“4th fibonacci number is “+fibonacci(4));
}

In the above code, we are creating a maintaining a log file or maintaining a lookup table and storing the values of computed results. Since we have memorized all the computed values, we can use them in the future if required, hence avoiding duplicate computations and overlapping subproblems.

All the logic is similar to the recursive solution, but the only difference we made is we are noting them in the memo array before we return the value to the main method. The only constraint to this algorithm is we need an extra space of size O(n), but we are optimizing the previous recursive solution.

Tabulation

This method is a little different than the above solution. Memoization follows the same recursive solution. But in tabulation, we follow an iterative solution. It is also called the bottom-up approach. Let us look at the implementation of the bottom-up approach.

public static int fibonacci(int n){
        int table[]=new int[n+1];
        for(int i=0;i<=n;i++){
            if(i==0 || i==1)
                table[i]=i;
            else{
                table[i]=table[i-1]+table[i-2];
            }
        }
        return table[n];
    }
public static void main(String[] args){
System.out.println(“4th fibonacci number is “+fibonacci(4));
}

As we know that fibonacci(n)=fibonacci(n-1)+fibonacci(n-2), In memoization we started with fibonacci(4) function call, and then we realized that we haven’t computed its value, so we’ve computed its values and then stored it.

A similar situation will be faced by further recursive calls like fibonacci(3), fibonacci(2). Now that makes a lot of recursive calls wait in the recursion stack, but anyways we are skipping the duplication of the overlapping subproblems.

We also have a way to compute fibonacci from 0 to nth element iteratively and then return the nth fibonacci element. This is what we’ve implemented in the above code. This code also has the same space requirement O(n).

Checkout: Skills to become a full stack developer

Optimal Substructure

In this concept, we can obtain an optimal solution to a problem only if we have optimally solved its corresponding subproblems.

And a classic example of this concept is considering a traversal between nodes in a graph.

Let us assume that we have multiple roots from Telangana to Delhi. And if we have the shortest route which passes through Nagpur and Gwalior. Then the shortest route from Nagpur to Delhi Delhi must pass through Gwalior. Now we can split our problem into subproblems which are Telangana to Nagpur, Nagpur to Gwalior, Gwalior to Delhi.

And a classic example for this property is the longest common subsequence in both strings. A subsequence is different from a substring. In a subsequence, the characters need not be consequent in the original string.

So the idea is to solve it by solving its subproblems optimally. Let n be the length of the longest common subsequence.

If n=LCS(potato, tattoo), then n=LCS(potat,tatto)+1 (if the last characters are same), else n=maximum(LCS(potato,tatto), LCS(potat, tattoo).

static int lcs(String s1, String s2, int m, int n ){
    int dp[][] = new int[m+1][n+1];
    for(int i=0; i<=m; i++){
      for(int j=0; j<=n; j++){
        if(i == 0 || j == 0)
            dp[i][j] = 0;
        else if(s1.charAt(i-1) == s2.charAt(j-1))
            dp[i][j] = dp[i-1][j-1]+1;
        else
            dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
      }
    }
  return dp[m][n];
  }
public static void main(String[] args){
System.out.println(“legth of longest common subsequence is “+lcs(“potato”,“tattoo”,6,6));
  }

In the above code, we’ve implemented our logic using the tabulation method and computed the length of the longest common subsequence present in both strings.

Also Read: Full Stack Developer Salary in India

Conclusion

Now that you are aware of using one of the powerful techniques to conquer the battle of efficient code, try implementing dynamic programming for other problems and start strengthening your ability to code a question using dynamic programming.

To conclude, Full Stack Developers are highly skilled experts who can handle everything related to web development. These Full Stack Developer skills are what distinguishes them from Frontend and Backend Developers.

Land on Your Dream Job

UPGRAD AND IIIT-BANGALORE'S PG DIPLOMA IN FULL STACK DEVELOPMENT
LEARN MORE

Leave a comment

Your email address will not be published.

×