The best way to approach Dynamic Programming is to thoroughly understand the entire process and all of the options available to you when implementing DP.
Once you’ve studied the basics, you can continue to learn. But a critical component in your approach should be testing yourself. Make sure you are implementing DP into problems that you are practising. Practising will enhance your learning of DP and give you the best approach to gain a complete understanding of the topic.
Provided below is an excellent starting point for your approach towards Dynamic Programming from AlgoMonster.
What Is Dynamic Programming?
Dynamic Programming is simply the act of breaking down complex problems into smaller problems so that you can solve them quickly and reuse solutions rather than calculating the same thing over and over again.
DP is an algorithm used in real life and also a prevalent coding interview topic. So it’s well-worth understanding and learning not only how it works but the concepts behind it.
Where Did the Name Come From?
Dynamic Programming isn’t originally a computer science term. Instead, it’s a math term that has been hijacked. The original meaning was related to solving large problems by breaking them into smaller problems to solve more easily.
So Dynamic Programming lives up to its stolen name.
How Do You Tell When To Use Dynamic Programming?
In most cases, it’s simple to tell if dynamic programming is going to add optimization to your code. It must pass two checks that you can quickly make on your problem.
This is the most simple test, so as you learn more about dynamic programming as well as other algorithms, you will be able to have a more intuitive approach to when DP should or can be used.
Optimal Substructure
Your problem can be broken up into smaller problems, which can be used together to solve the larger problem.
Overlapping Subproblems
The subproblems overlap, meaning the solutions to one can be used by many.
How Do You Solve Dynamic Programming Problems?
Dynamic Programming problems can be solved using two main methods—the Top-Down or Memoization approach and the Bottom-Up or Tabulation approach.
Both approaches have merit, and you would need to review what is best for your specific problem.
Top-Down with Memoization
This could be described as Depth First Search (DFS) with memoization. You basically split large problems into smaller subproblems and use recursion to solve the subproblems. Once the subproblems are solved, you can use the results to solve the main problem.
Bottom-Up with Tabulation
You take the problem and break it down into the simplest possible version of the problem, using the restrictions from the variables provided. You then solve the simple problems and use the solutions to start solving more complex problems.
Should You Do Top-Down or Bottom-Up?
Whether you use the Top-Down or Bottom-Up approach depends entirely on what you’re doing and what you think the best approach will be. So take a look at both methods, even implement both, and see which works best for your problem.
How Do You Develop An Intuitive Approach to Dynamic Programming?
The best way to develop an intuitive approach to dynamic programming is to learn and practice as much as possible. Many developers consider DP to be simple; however, it’s only as simple as you make it and how much knowledge you have about it and other algorithms.
To assist you in becoming more intuitive, make sure you’re practising with common DP problems, such as longest common subsequence, knapsack, and longest increasing subsequence.
Memoization
- With memoization, you don’t need to worry about the order of processing subproblems. So it’s a more straightforward implementation process.
- Memoization has a drawback in that it can be slower and take up more memory and even lead to stack overflows.
Tabulation
- It’s easier to calculate time complexity because you know it’s doing everything, so it’s just a matter of understanding how long that will take.
- With no recursions, there are no stack overflows.
- Implementation is much more complex, and you often need to implement memoization first and then add tabulation afterward.
Greedy Algorithms and Dynamic Programming
A greedy algorithm is one that always wants to choose the best answer. The difference between greedy algorithms and dynamic programming is that we’re calculating every state of the problem and not always looking for the best solution. Therefore, you can determine which algorithm is better for your solution by implementing DP and then making it always picking the best solution to see if that meets your optimization requirements.
Divide and Conquer and Dynamic Programming
Dive and conquer is another algorithm that breaks the main problem into subproblems to process. However, with dynamic programming, the subproblems overlap, but in dive and conquer, they will not.
When Should You use Dynamic Programming?
As you can see, at least two other algorithms are doing similar things that may work better depending on what you need to optimize and what your problem is. We discussed using optimal substructure and overlapping subproblems to help determine. Some more checks can be seen below.
- The problem uses dynamic values of biggest/smallest, such as maximum, minimum, longest, shortest, and things like cost or profit.
- If you implemented a greedy algorithm, but you’re sometimes getting an incorrect solution. This will generally mean you need to get optimal solutions for your subproblems.
- A particular problem that is almost always needing dynamic programming is the optimal way to play games.
Final Thoughts
As you can see, DP should be approached as a great tool that can optimize your code and help in coding interviews. However, you also need to understand that dynamic programming is not always going to be the best solution. Hence, you need to have a thorough understanding of DP and other standard algorithms that may work better in various situations.
You should be learning about, practising, and trying to implement different algorithms into your code so that you can continue to learn and grow, as well as provide optimized code to your employer.
