Steps to solve any Dynamic Programming Problem
Step 1: Recognize a DP problem
Recognizing that a problem can be solved using DP is the first and often the most difficult step in solving it. What you want to ask yourself is whether your problem solution can be expressed as a function of solutions to similar smaller problems.
Step 2: Identify problem variables
Now we have established that there is some recursive structure between our subproblems. Next, we need to express the problem in terms of the function parameters and see which of those parameters are changing.
If only 1 parameter is changing with each recursive call, the problem is 1D DP, similarly, if 2, 3 changing parameters are there, we have a 2D, 3D DP problem respectively.
A way to determine the number of changing parameters is to list examples of several subproblems and compare the parameters. Counting the number of changing parameters is valuable to determine the number of subproblems we have to solve. It’s also important in its own right in helping us strengthen the understanding of the recurrence relation from step 1.
Identify the changing parameters and determine the number of subproblems.
Step 3: Clearly express the recurrence relation
This is an important step that many rush through in order to get into coding. Expressing the recurrence relation as clearly as possible will strengthen your problem understanding and make everything else significantly easier.
Once you figure out that the recurrence relation exists and you specify the problems in terms of parameters, this should come as a natural step. How do problems relate to each other? In other words, let’s assume that you have computed the subproblems. How would you compute the main problem?
Recurrence relation: Assuming you have computed the subproblems, how would you compute the main problem?
Step 4: Identify the base cases
A base case is a subproblem that doesn’t depend on any other subproblem. In order to find such subproblems, you typically want to try a few examples, see how your problem simplifies into smaller subproblems, and identify at what point it cannot be simplified further.
The reason a problem cannot be simplified further is that one of the parameters would become a value that is not possible given the constraints of the problem.
Step 5: Decide if you want to implement it iteratively or recursively
The way we talked about the steps so far might lead you to think that we should implement the problem recursively. However, everything that we’ve talked about so far is completely agnostic to whether you decide to implement the problem recursively or iteratively. In both approaches, you would have to determine the recurrence relation and the base cases.
To decide whether to go iteratively or recursively, you want to carefully think about the trade-offs.
Step 6: Add memoization
Memoization is a technique that is closely associated with DP. It is used for storing the results of expensive function calls and returning the cached result when the same inputs occur again.
Step 7: Determine Time complexity
There are some simple rules that can make computing time complexity of a dynamic programming problem much easier. Here are two steps that you need to do:
- Count the number of states — this will depend on the number of changing parameters in your problem
- Think about the work done per each state. In other words, if everything else but one state has been computed, how much work do you have to do to compute that last state?
Lastly,
Work on more DP problems by following the steps we went through. You can always find a bunch of them online (ex. LeetCode or GeeksForGeeks). As you practice, keep in mind one thing: learn ideas, don’t learn problems. The number of ideas is significantly smaller and it’s an easier space to conquer which will also serve you much better.
