Maybe you've heard the term Dynamic Programming somewhere and wonder what it is. In this first post of the Dynamic Programming Series, I will attempt to explain what it is exactly and why is it so important. Personally, I definitely need more practice with this and that is why I am starting this series so that we can learn and master it together!

So What is Dynamic Programming?

Simply put, Dynamic Programming is a technique of breaking down a problem into subproblems, solving these subproblems once, and storing their solutions. You might ask why do we need to store these solutions? Well, in Computer Science, we define something to be efficient if it is fast and takes up little memory. By storing these solutions, we are able to simply look it up if the same problem resurface and this saves a lot of computation time because there is no need to recompute the solution. But wait! Efficiency consists of BOTH time and space complexity, so why does it matter if we reduce the time it takes to solve the problem only to increase the space used. This is why it's important to understand that in Dynamic Programming, what we are ultimately hoping to achieve is a significantly faster computation time at the expense of a modest increase in space used.

Approaches

There are essentially two ways you can go about in storing solutions to problems, and they are:

1. Memoization (Top-Down Approach)
2. Tabulation (Bottom-Up Approach)

In the Top-Down Approach, the general code structure would look something like:

def top-down(n):
if memo[n] is not initialized:
    # the epsilon below represents some computation that you do which is stored in memo
    # usually the computation will involve some recursive call that approaches the base case
    memo[n] = ... 
return memo[n]

Because this approach involves solving subproblems by tracing back to the base case, it is called a top-down approach. When we want to find a solution to the nth problem, we search for an answer to the n-1 th, n-2 th problem, and so on until the base case.

In the Bottom-Up Approach, it is simply the opposite. We first compute solutions to all the possible base cases and then work up from there to reach the solution we want. A general code structure for the tabulation approach would look something like:

def bottom-up(n):
    for i = 1 to i = n:
        table[i] = ...
    return table[n]

So now that you know the two approaches to DP, which approach should you use? As with almost any answer, it depends. Generally, you would want to use the top-down approach if not all solutions to subproblems need to be computed. This would save unnecessary computation time that is needed when using the bottom-up approach. Conversely, you should use the bottom-up approach if solutions to all subproblems need to be computed anyways since it prevents recursive call overheads that would almost always make the bottom-up approach faster.

At this point, I believe you've learned all you need to know about Dynamic Programming such that we are ready to work on our first problem in the next chapter of the series. Thanks for reading and until then!