Dynamic Programming (DP) is relatively simple once you break it down and start understanding its concepts. But, first, you need to understand overlapping subproblems, solve them, and then use those solutions at algo. monster to solve your main problem.
The best way to develop an intuition for dynamic programming is to understand what DP is thorough. You also need to know when to implement it and how best to implement it. You should also be practising as much as possible with the techniques you learn.
Detailed below is a systematic approach to dynamic programming to help you enhance your intuition when dealing with it.
Steps In Solving DP Problems
Can You Solve The Problem With DP?
DP is a method used to solve complex problems by breaking them down and solving subproblems once and then storing the solution. It is used to improve performance or generally optimize your code.
A quick way to see if DP can help your problem is to check if it relates to things that suggest optimization, such as maximum, minimum, longest, shortest.
DP can be further tested against two key concepts, optimal structure, and overlapping subproblems.
Optimal Structure
Can a recurrence relation solve your problem? If so, you should be able to find the solution to your problem from the combination of solutions in your subproblems.
Overlapping Subproblems
When solving your problem, do you find that you are solving the same subproblems over and over again? If you do, then you have overlapping subproblems that could be optimized.
If all of this points to DP, you can review the problem further to see how best to optimize your code.
Backtracking and Recursion
Recursion and backtracking are essential concepts in DP, and you should take time to practice coding these concepts. Practising and getting familiar with everything used in DP is how you become intuitive with it, rather than scrambling to solve problems.
Recursion
In recursion, you create a function that keeps calling itself to find the simplest subproblem that can be solved within the confines of the variables of the problem. You’re looking for the base case, and this is recursion.
Backtracking
Backtracking uses recursion to search problems exhaustively. These problems must be evaluated in multiple ways to find the optimal solution. So with backtracking, we are searching for a valid solution, or we reach the base case, at which point we step one level up the recursive tree, which is called backtracking.
Approaching Dynamic Programming with Memoization and Tabulation
The two common approaches with DP are memoization and tabulation, also called the top-down and bottom-up methods.
Looking at recursion and backtracking, these are essential concepts, but they are not considered DP. For a solution to be considered DP, it must be solving subproblems once and only once.
Memoization (Top-Down)
Memoization is a combination of recursion and caching. For DP to work, you need to ensure that you have overlapping subproblems. Take an example problem and see how many times you solve the same subproblem.
Implement code to solve the problem once, and then store the solution for later use. For example, now you’ve implemented DP using memoization. Your code should also implement a check before solving subproblems to see if the solution is already available.
Memoization is the easiest solution because it comes across naturally by working through the problem and solving things as they come up, and then, of course, storing the results.
In this solution, we’re speeding up processing but taking up space or memory, which is generally acceptable unless you have low memory availability or huge complex problems that take up too much space.
Tabulation (Bottom-Up)
Tabulation takes a different approach and completely ignores recursion. In the tabulation approach, we solve all problems and store them in a table before we do anything else. So whether you needed the problem solved or not, it got solved.
Once the problems are solved and stored in a matrix, you use these solutions to solve larger problems and work your way back up to the main problem you need to solve. This is why tabulation is called the bottom-up approach; you’re starting at the bottom and working your way to the solution.
Tabulation is more challenging to implement and use intuitively. However, the benefits of tabulation are that it is more efficient in processing power and space used. So you’re unlikely to run into memory problems with it.
Steps to Implement Dynamic Programming
The important part once you understand the concepts of DP is how to implement them effectively. Take a simple problem and run through the steps below.
- Determine if DP makes sense for this problem. Using the methods we discussed above.
- Define the parameters of the problem. For example, how many variables are there in the problem? This will help you break it down into subproblems.
- Define the states of the problem. What are the options you can select in your subproblems?
- Set limits so you can find your base case. Make sure you have implemented checks so that you don’t have solutions going out of bounds of the variables.
- Implement a recursive solution to your problem
- Optimize your solution to include caching of results (memoization)
- Consider if you can use tabulation in your solution to optimize it further.
Final Thoughts
Dynamic programming takes practice but is simple; once you understand and have a complete understanding, your intuition with it will come as well.
The important things to remember with DP are:
- DP is an optimization solution to cache results, so you aren’t calculating the same thing over and over.
- Problems that will work well with DP follow the concepts above of optimal structure and overlapping subproblems.
- You have two main options in DP, which are memoization or tabulation. Both have pros and cons that you need to start learning about.
- Memoization is a recursive solution with caching.
- Tabulation solves all subproblems and stores them in a matrix, and then it starts to solve the main problem.
- Keep practicing and keep learning. Your intuition will come soon.
