If you are working in any computer science-related field, or studying any course related to computer science, solving complex programming problems is a must-have skill. It is required in most of your day-to-day tasks and activities as a professional.

In solving these complex problems, programmers rely on an arsenal of techniques and approaches to tackle complex problems, from using LinkedLists, HashMaps, HashSet, Graphs, Heaps, and Dynamic Programming (DP), the particular focus of discussion in this article. They are essential for anyone working in computer science or studying any related field.

If you are not aware of all these techniques yet, don't be intimidated! See the links below for my recommendations on valuable resources to learn from.

This article will help you understand Dynamic Programming (DP) and memoization, we'll explore how to harness the power of these techniques to write efficient and elegant code. Whether you're a seasoned developer or just starting, this is a must-read for anyone looking to improve their problem-solving skills.

A lot of upcoming professionals shy away from understanding its concept and using it in their day-to-day work and we can’t really blame them. It’s one of those concepts that can seem quite daunting at first but we are here to see what happens behind the scenes of DP and memoization. So, let’s get into it! 🚀

Defining Dynamic Programming?

Dynamic programming is a unique technique that efficiently solves complex problems by breaking them down into overlapping subproblems. Each subproblem must be solved only once and stored in a map or an array to avoid redundant computations of the subproblems.

You will see that the word subproblem is frequently used in this definition, hence, to understand dynamic programming, you need to first grasp the concept of subproblems. It plays a crucial role in understanding dynamic programming.

That said, let’s dig into what a subproblem is and the importance of storing the results of sub-problems. If you have been wondering where memoization comes in, it is here. Memoization is the technique of storing the values computed from the subproblems and reusing them where needed.

Subproblems upon Subproblems

Dynamic Programming is all about breaking a big problem into basic and simpler subproblems. Subproblems are smaller instances of the original problem that share some characteristics with the larger problem. These subproblems can be obtained by breaking down the original problem into smaller, more manageable parts. By solving these subproblems and storing their solutions in a map or an array (memoization), these solutions will build up on each other to give the final solution to the initial problem. This avoids redundant computations of the subproblems and optimizes the overall solution.

The idea of breaking down a big problem to find a simple subproblem can be quite tricky sometimes, so let’s quickly see a subproblem from one example dynamic problem.

Pretend you have a staircase where each step is a toll point where you have to pay a certain toll fee. Once you pay the fee, you can move up the staircase by either one or two steps. You can start from either the first stairs or the second stairs.

Problem: Find the minimum cost to reach the top floor

We are going to analyse this problem thoroughly in this article, so I will just give the subproblem now.

Subproblem: What is the minimum cost to go from steps i through n, where n is the top floor

When you focus on analysing the subproblem, you can now structure your thoughts around looking for the minimum cost of steps n-1 through n, n-2 through n, and so on.

Notice how easy it is to read the problem this way? In solving DP problems, you must make sure to use memoization to store the results of each subproblem and you can later use them to solve the original problem.

Let’s further observe the importance of memoization, we will consider a popular dynamic programming problem - The Fibonacci Sequence. The Fibonacci sequence is a sequence of numbers where each number is the sum of the two previous numbers. The sequence usually starts at 0 and 1, so the fibonacci sequence will go like 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89... Well, you get the point.

The first way to detect that a problem can be solved using the dynamic programming technique is to check that the problem has overlapping subproblems. Let’s first examine the straightforward recursive algorithm for solving a fibonacci sequence:

In this recursive solution, to find fibonacci(5) , we need to compute fibonacci(4) and fibonacci(3) , to compute fibonacci(4), we need to compute fibonacci(3) and fibonacci(2). At this point, we can already see some repeated work happening when we call fibonacci(3) twice. When we continue the recursive analysis of the sequence, we will see a lot of repeated work in the recursive solution as shown below:

In the diagram above, we will see that we are calculating fibonacci(2) three times! That’s a lot of unneeded computing for a job relatively as small as solving the fibonacci of 5. What if we could arrive at a solution that solves the fibonacci of 2 once, stores its result, and accesses it wherever fibonacci of 2 is needed again?

Let’s examine the dynamic programming version of this algorithm:

Notice how we initiated a HashMap with the two results that we already know, 0 and 1, and starting from the 3rd item in the sequence(index 2), we can iteratively loop through the values from 2 to n. For every value from 2 through n, we will use the existing results to get the value and store the current solution right back into the HashMap for the next value to use.

With this approach, we only need to iterate over the range of n once and solve for all the values we need as we go. It has a time complexity of O(n), which is more efficient.

We implemented memoization here by introducing the HashMap to store results. Memoization forces us to not recompute subproblems, but the real hack of dynamic programming is the ability to find the right subproblem to take care of all the requirements of the bigger problem.

Since we now understand subproblems and memoization, let us do a behind-the-scenes and dive into practical steps to arriving at a dynamic programming solution. We will go through my five personal steps to solving dynamic programming problems, using the climbing stairs problem I earlier gave.

• Visualise the problem naively to identify the repeated work

• Find the appropriate subproblem

• Find the mathematical relationship among the subproblems

• Generalise the mathematical relationship (for every value of n)

• Find the correct order to implement the formula (bottom-up/top-down)

• Return the solution to the original problem

Step1: Visualizing the problem naively to identify the repeated work

Programmers, too often, go right into punching the keyboard and churning out the most naive thoughts they can gather. While this might be somewhat helpful, I always prefer to have a visual example of the problem.

As we did with the Fibonacci sequence where we graphically analysed how each function will be called at every point of the algorithm, we will do here as well. Let's read the problem again and see how we can arrive at a visual example of the situation, stating its critical parts:

• A staircase, each having a cost

• we can start from the first or second step

• we can climb either 1 or 2 steps at a time

• we need to reach the top floor

Naively, we can visualize the problem as thus:

From this visualization, you would find that it is easier to see how the progression of the climbing should go and what amount of steps can take us to the top floor. Can we already Identify a repeated work, just from this visualization?

Absolutely! We can already see that there are two situations where we arrive at the step of index 2, this means that the remaining part of those two situations will be exactly the same and if we naively continue each of those scenarios, we will be doing the exact same work twice! Because the cost of reaching the top floor from the step at index 2 will always be the same wherever it is needed and the same applies to every index i

That leads us to the second step.

Step 2: Finding the appropriate subproblem

We have already identified, in the previous step, that the repeated work involves getting the cost to reach the top floor at any index i. Depending on the number of steps you take per time (1 or 2), you can have different minimum costs for every index i but according to the problem what we need is the minimum, so we only take the smallest amount.

And that produces the appropriate subproblem:

"What is the minimum cost to go from the step at index i through n, where n is the top floor?"

Now that we have the subproblem in words, we will move on to getting the mathematical relationship between the subproblems at every index.

Step 3: Find the mathematical relationship among the subproblems

From the subproblem determined above, I create a mathematical formula by asking some questions, how can I get the cost from n-1 through n, and then from n-2 through n, then n-3 through n? What do I do at each of those steps? If my algorithm is at index i, what information does it need to handle index i+1, or in some cases, i-1?

Let's answer those questions regarding our current problem.

To arrive at n from n-1, I already know that I need only 1 step and I also already know that the minimum cost I can have will surely include the cost at step n-1. This means that, at the very least I will spend the cost of the present step to reach the top floor n. And that is true for all values of i through n.

Next, to arrive at n from n-2, the minimum cost will be the cost at step n-2 together with the minimum cost between taking 1 step and taking 2 steps. If we take only one step, we will land at step n-1, which is already the step, we calculated earlier. We already calculated the result of that and can use it again here.

We can interpret it mathematically into the following.

F(n-2) = cost[n-2] + min(cost[(n-2) + 1], cost[(n-2) +2])

where F(n-2) is the solution of n-2

Step 4: Generalise the mathematical relationship

Now that we have found the formula, we can generalise this formula for every value of i through n. Therefore, for every value of i, we can create a formula, F(i)

F(i) = cost[i] + min(cost[i+1], cost[i+2])

that answers the question; "what do I need to solve for index i?"

Step 4: Find the correct order to implement the formula

There are typically two orders to implement the formula:

• Bottom-up

• Top-down

Their names are pretty self-descriptive. For our stairs scenarios, you may expect that we have a bottom-up approach but this will not be beneficial to us because according to our formula, we need to have the solutions for i+1 and i+2 before we can solve for i itself. So, we will have to solve from the top of the stairs down.

Step 5: Write the Code, Return the solution to the original problem

At this point, we already have what it takes to write the code, so let us combine all the information we have so far.

Recall our mathematical formula: F(i) = cost[i] + min(F[i+1], F[i+2])

Also, recall the values we already know:

the top floor, n, has a cost of 0 and the last step before the top floor, n-1, has the cost of itself as the minimum cost.

Normally, for this kind of problem, you would be given an array of the cost of each step. Let's consider the following array: [10,15,20]

This translates into having three steps before the top floor, if you check the analysis diagram you saw earlier, you would notice that the top floor was in another colour (green), different from the colour of the steps (white).

But we know that the minimum cost for that level is 0, so we can add that to the set of values we are given and our new array would be: [10, 15, 20, 0]

What we have done here is that we have initialized our array to have the least cost any step can have at any given point. Recall that, in Step 3, we said that at the very least, we will spend the cost of each step before taking the next 1 or 2 steps and that is what we have achieved with the new array we have.

Now, we can use the formula in Step 3 and use the order we derived in Step 4, the top-down order.

for step, n, which is the top floor, we have already filled it as 0, for the step right after the top floor, we also already know that the most optimal solution for its minimum cost is the cost at that step because we can take just one step to reach the top floor.

We can same the same for the next step downward, the most optimal solution will be the cost at that step because we can take 2 steps from that step to reach the top floor. We know this because we are sure that this is logically true for all cases in this problem.

Since we know that, we don't need to compute those values, we can simply start implementing our formula from the third step after the top floor. See the diagram below for better comprehension.

Let us write the code for the facts we have.

First, we add the value for the top floor to the array and create the minimum cost for all steps:

def climb(cost):
    # append 0 to the array to create
    # minimum cost for every step
    cost.append(0)

Next, we start from the third step and use our formula to fill all the steps from top to down:

def climb(cost):
    # append 0 to the array to create
    # minimum cost for every step
    cost.append(0)
    # iterate from the third step
    # and use formula to fill optimal solutions
    # by updating the cost array at that step
    # with the minimum cost to reach top foor from that step
    for i in range(len(nums)-3, -1, -1):
        cost[i] += min(cost[i + 1], cost[i + 2])

And that is all. All we need to do now is to return the solution to the original problem.

Let's take a step back here and read the problem again, to save you the stress of scrolling back up, this is the problem:

Pretend you have a staircase where each step is a toll point where you have to pay a certain toll fee. Once you pay the fee, you can move up the staircase by either one or two steps. You can start from either the first step or the second step.

The edge case here is that we can start from either the first step or the second step, but we need the minimum between starting from step one and step two to reach the top floor.

Luckily for us, when our algorithm runs till the end of the loop, it would have already calculated the minimum cost for both step one and step two to reach the top floor, hence, we only need to find the minimum and return that as our solution.

Let's do that:

def climb(cost):
    # append 0 to the array to create
    # minimum cost for every step
    cost.append(0)
    # iterate from the third step
    # and use formula to fill optimal solutions
    # by updating the cost array at that step
    # with the minimum cost to reach top foor from that step
    for i in range(len(nums)-3, -1, -1):
        cost[i] += min(cost[i + 1], cost[i + 2])
    # we have solved for all steps
    # now, we can return the minimum between
    # step one to reach top floor and
    # step two to reach top floor
    return min(cost[0], cost[1])

Testing the algorithm with the array we analyzed earlier; [10, 15, 20]. Our minimum should be 15. This is true because we can take 2 steps from the second step to reach the top floor.

Memoization vs Dynamic Programming

Did you spot where the memoization happened in our previous solution above? We reused the cost array we got as input as the base case values for all steps. You may be wondering if you can do that for all DP problems. Well, not really, not all DP problems will take the same shape as this and you may not be able to reuse the input value. This means that you will most likely need to create a new array or HashMap to store some computed values as we did in the Fibonacci algorithm above.

While creating new HashMaps for DP problems, you can easily confuse pure memoization techniques that are non-DP patterns, they usually appear as a recursive solution but with memorized solutions. The first time I encountered the same question we are analyzing right now, I wrote the brute-force solution and then optimized it to this recursive-memoization mix.

This is what it looked like:

def memo_rec_climb(cost):
    # initialize memoization variable
    memo = {}
    #  store default memoization values
    memo[len(cost) - 1] = cost[-1]
    memo[len(cost) - 2] = cost[-2]

    def minCost(i):
        # attempt to read value from memo first
        if i in memo:
            return memo[i]
        # using the formula for every value of i
        memo[i] = min(minCost(i + 1), minCost(i + 2)) + cost[i]
        return memo[i]

    for i in range(len(cost) - 3, -1, -1):
        # starting the loop from the 3rd step
        minCost(i)
    # return minimum between starting from step 1 and step 2
    return min(memo[0], memo[1])

This version is overall way more efficient than the recursive brute force solution but I'm sure you would agree, that it is relatively more cumbersome than the DP solution we wrote above. Also, when it comes to execution speed, the DP solution is 2 times faster than the recursive-memoization mix.

We will quickly discuss more details on the runtime analysis of DP solutions in the next section.

The major difference is that Memoization stores value for future use, avoiding recomputation while Dynamic Programming uses Memoization to achieve a more optimal solution.

Not all recursive functions can be optimized using the Dynamic Programming technique. There are two requirements we need to consider before using the Dynamic Programming approach:

• Overlapping Subproblems

• Optimal Substructures

If the recursive solution doesn't meet the above requirements, then it can not be solved using a Dynamic Programming approach.

Runtime Analysis of Dynamic Programming

In calculating the runtime analysis here we will be using the good old big-O notation. If you've never encountered big-O before, don't worry it's just a not-so-boring math used to measure code's efficiency.

In calculating the general runtime for dynamic programming, we need to consider the following parameters:

• Pre-processing

• How many times the for-loop runs

• how long it takes to run the recurrence of an iteration in the for-loop

• Post-processing

The total formula to calculate the runtime is:

pre-processing + loop * iteration + post-processing

Let's analyze the runtime for our dynamic programming problem.

Pre-processing: appending the cost of the top floor: O(1)

Typically, this will be an O(n) operation if we created another array to store the default values, like this:

def climb(cost):
    # create base values with memo
    memo = [0] * len(nums) + 1
    for i in range(len(nums)):
        memo[i] = nums[i]

But we have reduced all that complexity by re-using the input cost array

How many times the iteration runs; That's also linear time: O(n)

How long it takes to run the recurrence of an iteration in the for-loop: for each iteration, we are making a decision between two options, climbing one step or climbing two steps, that is a constant operation for every value of n: O(1)

Post-processing: worst case scenario, O(n)

Using the runtime formula, we have: O(1) + O(n) * O(1) + O(n)

That sums up to O(2n) but we can ignore the two and the time complexity will finally be O(n)!

Congratulations! 🥂

Yes, you did it!

With your newfound understanding of dynamic programming, you're well on your way to becoming a true wizard in this problem-solving realm. Remember, practice makes perfect, and the more you delve into dynamic programming, the more natural it will become to identify sub-problems and recurrence relations.

Dynamic programming may initially seem daunting and frustrating, but fear not! Embrace the challenge and keep honing your skills by writing dynamic programs repeatedly. As you do, you'll find that the patterns and techniques start to become second nature, empowering you to tackle even the most complex problems with confidence.

If you need more resources on dynamic programming and other useful algorithms, I highly recommend studying with NeetCode.io

If you enjoy what you read. Please spread the love by liking and sharing this piece. If you have thoughts or questions, please reach out to me on Twitter or in the comments below.