How to solve a dynamic programming problem - javatpoint
Dynamic programming is an optimization technique developed by Richard Bellman in the 1950s. Basically, dynamic programming is an optimization over the normal recursion. In the case of recursion, repeated calls are made for the same sub-problem, but we can optimize this problem with the help of dynamic programming. The idea behind using dynamic programming is that we store the results of sub-problems so that we do not need to re-compute the sub-problem whenever required. This reduces the time complexities from exponential time to linear time.
Below is the code of Recursion with exponential time.
Below is the code of dynamic programming with linear time.
Techniques to solve a dynamic programming problem.
To solve any dynamic programming problem, we can use the FAST method.
Here, FAST stands for:
The above three steps are used for the top-down approach if we use 'F', 'A' and 'S', which means that we are achieving the Top-down approach. Since it is not purely because we are using the recursive technique.
Above are the four steps to solve a complex problem.
As we know that Fibonacci series looks like:
0, 1, 1, 2, 3, 5, 8, 13, 21,...
First, we find the recursive solution,
The below is the code of the above recursive solution:
The above recursive solution is also the solution for the above problem but the time complexity in this case is O(2n). So, dynamic programming is used to reduce the time complexity from the exponential time to the linear time.
Second step is to Analyse the solution
Suppose we want to calculate the fib(4).
Fib(4)= fib(3) + fib(2)
Fib(3) = fib(2) + fib(1)
Fib(2) = fib(1) + fib(0)
As we can observe in the above figure that fib(2) is calculated two times while fib(1) is calculated three times. So, here overlapping problem occurs. In this step, we have analysed the solution.
Third step is to save the result.
The process of saving the result is known as memoization. In this step, we will follow the same approach, i.e., recursive approach but with a small different that we have used the cache to store the solutions so that it can be re-used whenever required.
Below is the code of memoization.
In the above code, we have used a cache array of size n+1. If cache[n] is not equal to zero then we return the result from the cache else we will calculate the value of cache and then return the cache. The technique that we have used here is top-down approach as it follows the recursive approach. Here, we always look for the cache so cache will be populated on the demand basis. Suppose we want to calculate the fib(4), first we look into cache, and if the value is not in the cache then the value is calculated and stored in the cache.
Visual representation of the above code is:
Fourth step is to Tweak the solution
In this step, we will remove the recursion completely and make it an iterative approach. So, this technique is known as a bottom-up approach.
In the above code, we have followed the bottom-up approach. We have declared a cache array of size n+1. The base cases are cache[0] and cache[1] with their values 0 and 1 respectively. In the above code, we have removed the recursion completely. We have used an iterative approach. We have defined a for loop in which we populate the cache with the values from the index i=2 to n, and from the cache, we will return the result. Suppose we want to calculate f(4), first we will calculate f(2), then we will calculate f(3) and finally, we we calculate the value of f(4). Here we are going from down to up so this approach is known as a bottom-up approach.
We can visualize this approach diagrammatically:
As we can observe in the above figure that we are populating the cache from bottom to up so it is known as bottom-up approach. This approach is much more efficient than the previous one as it is not using recursion but both the approaches have the same time and space complexity, i.e., O(n).
In this case, we have used the FAST method to obtain the optimal solution. The above is the optimal solution that we have got so far but this is not the purely an optimal solution.
Efficient solution:
The above solution is the efficient solution as we do not use the cache.
Digital Marketing
Elasticsearch
Entity Framework
Firewall
Functional Programming
Google Colab
Graph Theory
Groovy
Group Discussion
Informatica
Ionic
ITIL
IOS with Swift
Angular Material
Deep Learning
Aptitude
Reasoning
Verbal Ability
Interview Questions
Company Questions
Artificial Intelligence
AWS
Selenium
Cloud Computing
Hadoop
ReactJS
Data Science
Angular 7
Blockchain
Git
Machine Learning
DevOps
DBMS
Data Structures
DAA
Operating System
Computer Network
Compiler Design
Computer Organization
Discrete Mathematics
Ethical Hacking
Computer Graphics
Software Engineering
Web Technology
Cyber Security
Automata
C Programming
C++
Java
.Net
Python
Programs
Control System
Data Mining
Data Warehouse
Website Development
Android Development
Website Designing
Digital Marketing
Summer Training
Industrial Training
College Campus Training
Address: G-13, 2nd Floor, Sec-3
Noida, UP, 201301, India
Contact No: 0120-4256464, 9990449935
© Copyright 2011-2021 www.javatpoint.com. All rights reserved. Developed by JavaTpoint.
