Programs

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

Learn Software Development Courses online from the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs, or Masters Programs to fast-track your career.

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 Courses 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.

What is dynamic programming?

A computer program contains a lot of repetitive code. This is inefficient and may impact its performance. In this case, dynamic programming is used. Dynamic programming is a method of solving a complex problem by breaking it into simpler sub-problems, solving each of these sub-problems just once, and storing their solutions using tables, which are then looked up whenever a similar sub-problem occurs later in the solution of the complex problem. Dynamic programming algorithms are used to solve various types of optimization problems in the fields of operational research, statistical estimation, pattern recognition, artificial intelligence, machine learning, computational biology, and other fields.

What is overlapping subproblem in dynamic programming?

The overlapping subproblem is a concept used when subproblems have solutions which are used in other subproblems as well. This overlapping causes the same subtask to be solved more than once. The problem is to find a way to solve the subtask only once, and use that solution to get the solutions of other subproblems. Dynamic programming algorithms solve this problem using memoization. Memoization is a technique where we store solutions to subproblems so that we do not have to solve them again.

What is optimal substructure in dynamic programming?

Optimal substructure implies that the optimal solution to a problem is related to an optimal solution to a smaller problem within the same problem definition. Optimal substructure is an additional requirement needed to solve problems or to prove that there is no solution. With optimal substructure, we can prove many problems NP-hard. A general approach to solve DP problems is to use dynamic programming matrix to store the optimal solution of subproblems. Dynamic programming matrix can be used to solve any nonzero optimal substructure DP problems.

Want to share this article?

Land on Your Dream Job

Leave a comment

Your email address will not be published. Required fields are marked *

Our Popular Software Engineering Courses

Get Free Consultation

Leave a comment

Your email address will not be published. Required fields are marked *

×
Let’s do it!
No, thanks.