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.
How does the dynamic programming approach work?
The dynamic programming approach works in steps mentioned below:
1. Break down the problem: Breaking down the problem is the first step in dynamic programming. You take the big, complex problem and divide it into smaller, more manageable subproblems. Each subproblem is a simplified version of the original problem, focusing on a specific part or a smaller input size. By solving these subproblems, you gradually build up the solution to the main problem.
2. Identify overlapping subproblems: The next step is to identify overlapping subproblems. These are the subproblems that you encounter repeatedly while solving the main problem. Dynamic programming relies on the fact that many complex problems have overlapping subproblems. By recognizing these overlaps, you can avoid solving the same subproblems multiple times, which saves a lot of time and effort.
3. Solve subproblems and store results: Once you've identified the subproblems, you start solving them one by one. As you solve each subproblem, you store its result in a table or some other data structure. This table acts as a memory, allowing you to recall the solutions to subproblems whenever you need them in the future. By storing the results, you avoid redundant calculations and make the problem-solving process much more efficient.
4. Reuse stored results: As you progress towards solving the main problem, you'll encounter subproblems that you've already solved before. Instead of solving them again, you simply retrieve their results from the table where you stored them earlier. This is where the power of dynamic programming shines. By reusing previously computed results, you save a tremendous amount of time and computational resources.
5. Combine subproblem solutions: Finally, you combine the solutions of the subproblems to solve the main problem. This is like putting together the pieces of a puzzle. You take the results you stored from solving the subproblems and use them to build up the final answer. The combination process varies depending on the specific problem, but it typically involves some mathematical operations or logical reasoning.
Approaches of dynamic programming
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;
}
You can also try this code with Online C++ Compiler
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);
}
You can also try this code with Online C++ Compiler
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];
}
You can also try this code with Online C++ Compiler
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 are the 4 dynamic programming languages?
Dynamic programming languages are those that execute many common programming behaviors at runtime that static programming languages perform during compilation. Four popular dynamic languages are Python, JavaScript, Ruby, and PHP. These languages are highly flexible, making them ideal for rapid application development and scripting.
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 discussed the concept of dynamic programming, discussed the types of problems it can solve effectively. We also compared dynamic programming with recursion to highlight their differences and when one might be more suitable than the other. Moreover, we looked at various problem scenarios where dynamic programming can be applied, which clearly shows why DP is very effective and effectiveness in solving complex computational problems.
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!"
46+ registered 