Introduction
A dynamic problem is an algorithm for solving harder and bigger problems by dividing them into smaller subproblems, keeping in mind that the optimal solution to bigger problems lies in smaller subproblems. We store the answer for the overlapping subproblems and use that result if we need the answer for the same problem in the future. The main idea is to avoid repetitive computations. The key components of dynamic programming are Recursion as well as Memoization. Hence,
Dynamic programming = recursion + memoization
What Kind of Problems DP Solves?
Dynamic Programming can solve problems that exhibit a specific structure where a problem can be broken down into smaller subproblems that are similar to the original problem. The very first and important step is to figure out that the problem can be solved using Dynamic Programming. After you figure it out, then there are two approaches for solving dynamic problems:
- Bottom-up dynamic programming: In this method, we begin with the smallest possible solution, which is known to us. After that, we find out the next values by utilizing the previously calculated values, which are, in this case, stored in a tabular structure.
- Top-down dynamic programming: In this method, the problem is simply broken down into smaller subproblems to the extent of the base case for which the return value is known. This value is then stored in order to use it for previous computation.
Is Dynamic Programming just Recursion?
Recursion is when a function can be called and executed by itself, while dynamic programming is the process of solving problems by breaking them down into sub-problems to resolve the complex one. Dynamic programming can function even without Recursion. Dynamic programming is the optimization technique that makes the previously calculated value in use in order to save time. In dynamic programming, a problem is broken into smaller subproblems, and that is what is called a Recursion.
Ways to Solve Dynamic Programming Problems
There are two different ways to store the values so that the values of a sub-problem can be reused. Both are discussed below :
- Tabulation or Bottom-up: Bottom-up is a technique that saves memory by avoiding Recursion, which has been incurred by recursion call stack. Bottom-up means starting from the beginning.
- Memoisation or Top-down: Memoisation assures that a function doesn't run again for the same inputs again and again by keeping a record of the results for the previously given inputs.
Let's look at an example to clearly understand the concept:
Fibonacci Number Series:
Recursive approach
int fibonacci(int n) {
if (n <= 1)
return n;
int a = fibonacci(n - 1);
int b = fibonacci(n - 2);
return a + b;
}
Time-complexity : 2^n
Memoisation approach
int fib_helper(int n, int * ans) {
if (n <= 1)
Return n;
if (ans[n] != -1)
Return ans[n];
Int a = fib_helper(n - 1, ans);
Int b = fib_helper(n - 2, ans);
Return ans[n] = a + b;
}
int fib(int n) {
int * ans = new int[n + 1];
for (int i = 0; i <= n; i++) {
ans[i] = -1;
}
return fib_helper(n, ans);
}
Time-complexity : O(n)
Bottom-up approach
int fibo(int n) {
int * ans = new int[n + 1];
ans[0] = 1;
ans[1] = 1;
for (int i = 2; i <= n; i++) {
ans[i] = ans[i - 1] + ans[i - 2];
}
return ans[n];
}
Time-complexity : O(n)
In depth discussion of the difference between tabulation is memoization is given here
Check out Longest Common Substring
Variations of Dynamic Programming Problems
There isn't any set of variations of problems in which a DP problem lies but frequently asked problems have a certain set of variations we will be discussing below:
Stock Variation
In this type of problem variation, we are generally asked to calculate the maximum profit one can make from the given daily trading chart by setting the number of times one can buy or sell the stock. Now ,clearly it is asking for an optimised result and we are given with choices to pick the stock to buy or sell, therefore it is a variation of dynamic programming problem. Refer to this for more details.
Expression Matching
In this type of problem variation, we are asked to match two strings by setting some wildcard rules for some characters. Here, we have the choice to choose from which index we use this wildcard. Therefore it is a Dynamic programming problem. Refer to this for more details.
LCS and its variations
In this variation type, we are given two strings and maybe asked to calculate the longest common substring or maybe given one string and asked to calculate the longest palindromic substring. Here ,we are asked for an optimised result and are given with choices whether to pick the element or not in the final result. Therefore, it is a variation of dynamic programming problem. Refer to this for more details.
0-1 Knapsack and its variations
In 0-1 knapsack problem and its variations, we are given with an array and asked to get the maximum profit while picking elements from the array by setting constrain on either the money or weight or any such entity. Since, we are asked to get an optimised result by picking or not picking elements from the array. Therefore it is a dynamic programming problem. Refer to this for more details.
Must Read Julia Programming Language
Frequently Asked Questions
What is Dynamic Programming?
A dynamic problem is an algorithm for solving bigger problems by dividing them into smaller subproblems, keeping in mind that the optimal solution to bigger problems lies in smaller subproblems.
How is Dynamic Programming different from normal programming?
Dynamic programming is not "programming" in that sense. It is not about writing code, but the word "programming" there is used in the context of solving complex problems by breaking them down into simpler problems.
How to solve a Dynamic Programming problem?
The first step is to identify the problem. The next step is to identify what type of variation it is, if possible. By doing so, it would be easy to solve the problem.
Conclusion
In this article, we have discussed dynamic programming, what kind of problems can be solved by dynamic programming, the difference between DP and Recursion, and finally, variations of problems in Dynamic Programming.
Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available, interview puzzles, take a look at the interview experiences, and interview bundle for placement preparations.
We hope that this blog has helped you enhance your knowledge regarding puzzles, and if you liked this blog, check other links.
Do upvote our blog to help other ninjas grow.
Happy Coding!"
