7 Steps to solve a Dynamic Programming Problem

$\mathtt{REFERENCE}$ @ Medium

$\mathtt{REFERENCE}$ @ Refdash

I loved the way the article has explained on how to proceed with Dynamic Programming. I am listing some key points from the article (for my own reference).

7 Steps to solve a Dynamic Programming Problem

1. How to recognize a DP problem
2. Identify Problem variables
3. Clearly Express the reccurrence relation
4. Identify the base cases
5. Decide if you want to implement it iteratively or recursively
6. Add memoization
7. Determine time complexity

Step 1: How to recognize a Dynamic Programming problem

Recognizing a Dynamic Programming problem is often the most difficult step in solving it. Can the problem solution be expressed as a function of solutions to similar smaller problems?

First, let’s make it clear that DP is essentially just an optimization technique. DP is a method for solving problems by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution. This saves computation time at the expense of a (hopefully) modest expenditure in storage space.

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

After identifying some recursive structure between our subproblems, we need to express the problem in terms of the function parameters and see which of those parameters are changing.

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, but it is also important in its own right in helping us strengthen the understanding of the reccurrence relation from step 1.

Step 3: Clearly express the recurrence relation

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?

Step 4: Identify 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 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 constraints of a problem.

Step 5: Decide if you want to implement it iteratively or recursively

Step 6: Add memoization

Step 7: Determine Time complexity

---

Implementation for Problem Discussed in the Reference Page

---

---

---