Dynamic Programming(DP) itself sounds so huge that coders try to avoid it as far as possible. But big companies like Nutenix, Flipkart, Amazon love those coders who can code a solution that is both optimised and have a minimum time complexity.
Wondering what this post is about?
The title suits this post well, today we'll talk about how a noob coder can identify a DP problem and then approach towards solving it.
Firstly, let me tell you that DP is all about recursion:
DP = Enhanced Recursion
where Enhanced Recursion is basically calling a function itself with a simpler input.
Parent of a DP problem is Recursion. What do I mean by parent here? Every DP problem can be solved using recursion so it really matters for you to learn recursion first. Clear your concepts on Recursion then proceed to DP.
Secondly, identifying the question of DP
Keep these two things in mind while identifying:
a) Choice will be given like in a Knapsack problem which element to include and which one element shouldn’t be included.
b) Optimal Questions like those questions covering topics about Minimal, Maximum, Largest, Maximum Profit.
From recursion, Overlapping Recursion is a DP problem.
Now you must be wondering what is this overlapping recursion? Well it's basically a tree-like structure of a recursion function getting called two or more times and then overlapping each other while getting called up.
If the function is called and the program gets executed without even touching other recursion functions then that is called overlapping problem in recursion.
Let's get to the approach that should be used for solving a DP problem:
If you don't know this approach:
[#Recursive Solution---> Memoization]
then do not I repeat DO NOT use this approach to solve your question that is using a "Top down approach which means forming a matrix initially and then filling up the boxes assuming some conditions"
As a developer in making I would really like to add that without knowing Recursion, proceeding to DP is stupidity. You should have a recursive approach to proceed to a top down solution.
The standard form to solve any DP question is this:
Recursive Solution ---> Memoize ---> Top-Down Approach
The only difference between various DP variations question lies in the recursive code.
BONUS POINT
Different questions that you can try out learning are:
1) 0 1 Knapsack Problem(6)[this 6 means the different questions that includes variation with 0 1 knapsack]:
- Subset Sum
- Equal Sum Partition
- Count of Subset Sum
- Minimum Subset sum difference
- Target Sum(Leet Code Problem)
- Count number Of Subset with a given difference
2) Unbounded knapsack(5)
3) Fibonaaci(7)
4) LCS(Longest Common Sub-sequence)(15)
5) LIS(Longest Increasing Sub-sequence)(10)
6) Kadane's Algorithm(6)
7) Matrix Chain Multiplication(7)
8) DP on Grids(4)
9) DP on trees(14)
10) Others(5)
Ending this post while reminding you all to take care of yourselves and keep coding 💜
Top comments (2)
Thanks man! Really helpful 👍🏼
glad you found it helpful :)