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.
Check out our free courses to get an edge over the competition
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:
- Overlapping subproblems
- 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.
Check out upGrad’s Advanced Certification in Blockchain
| 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)
Explore Our Software Development Free Courses
Check out upGrad’s Advanced Certification in DevOps
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).
Explore our Popular Software Engineering Courses
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).
In-Demand Software Development Skills
| 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.
upGrad’s Exclusive Software Development Webinar for you –
SAAS Business – What is So Different?
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.
Read our Popular Articles related to Software Development
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.
![Spring Boot Annotations Everyone Should Know [2023]](https://prod-eks-app-alb-1037681640.ap-south-1.elb.amazonaws.com/blog/wp-content/uploads/2020/09/1000-300x170.png)
![Function Overriding in C++ [Function Overloading vs Overriding with Examples]](https://s3.ap-south-1.amazonaws.com/upgrad.prod.blog/blog/wp-content/uploads/2021/04/26074804/2042-2-300x170.png)
