In Dynamic Programming basics, we will cover the basics of DP and its differences from the Greedy method, Divide and Conquer and Recursion.
Dynamic programming is an approach just like recursion and divide and conquer. It divides the problem into subproblems. But instead of solving these subproblems independently like divide and conquer and recursion, it uses the results of previous subproblems for similar computations also known as an overlapping problem.
It is used for the optimization of programs. As it uses the previously computed results, using its exponential time complexity can be reduced to polynomial. For instance – The time complexity of the recursive solution of Ugly Numbers is exponential and of DP solution is linear.
Table of Contents
Some basic problems of DP
- Ugly numbers problem
- Coin change
- Fibonacci numbers
- Bell numbers problem
- Tower of Hanoi
- Bell numbers
- Knapsack problem
Dynamic Programming (DP) vs Greedy Method
In DP each step evaluates the solution considering the current as well as previous solutions to obtain the optimal solution. However, in the greedy algorithm, we select the best option considering only the current situation.
Although greedy methods are generally faster than DP and are also memory efficient as it does not store previously computed values for future use, it does not give assurance of an optimal solution.
Dynamic Programming (DP) vs Divide & Conquer Method
In divide and conquer we divide a problem into subproblems and solve each subproblem independently. However, in DP rather than solving problems independently, we use the previously obtained results for new computations. In other words, we can say Divide and Conquer + Memoization = top-down dynamic approach.
(Memoization refers to the technique of storing the previously computed results generally in hash-map to prevent the computations of the same problems over and over again. )
Dynamic Programming (DP) vs Recursion Method
DP stores the previously computed solutions to use them as and when required again in the future to avoid re-computations. However, in recursion, there is the possibility of having re-computations which is unnecessary as it does not store values.
Recursion leads to the re-calculation of problems several times therefore in such cases time complexity of recursion is always greater than DP solution.
In this article, we covered about Dynamic Programming basics. In the next articles, we will cover some basic problems on DP.