Dynamic Programming Techniques with Examples.

In this article we will discuss:

• What is Dynamic Programming?
• When to use Dynamic programming to solve coding problems?
• Methods of dynamic programming.
• Solve some coding problems.

Prerequisites:

Basic understanding of:

• Recursion.
• Complexity Analysis and Big O notation.
• Javascript ES6 syntax, closures.

What is Dynamic Programming?

It is an optimization technique used to solve recursive problems more efficiently.

It is mainly done by finding if there are any repetitive subproblems and if so we compute it only once and store the value. By doing that, we can avoid re-computing repetitive values and save lots of time.

The final result is we get an optimized solution with a polynomial time complexity instead of exponential time complexity resulting from Brute force recursion.

When to use Dynamic programming to solve coding problems?

1. If the problem can be divided into subproblems.
2. If we can implement a recursive solution.
3. There are repetitive subproblems.

The solution could be done either by:

• Using Memoization (top-down recursive approach).
• Or Tabulation (bottom-up iterative approach).

Methods of dynamic programming:

1-Memoization (recursive, top-down approach):

In this technique, we are still solving the problem recursively. But this time we are going to cache the result of each subproblem in order not to solve it again repeatedly.

When we encountered the same subproblem that we did before we just access its results from the cache instead of recomputing it again.

To make things clearer let implement the recursive brute force for Fibonacci numbers, then try to memorize it.

Recursive tree structure for 7th Fibonacci number which results in 13.

Each number in the Fibonacci sequence equals the summation of the previous two numbers. fib(n) = fib(n-1) + (fib(n-2).

With our base cases if fib(0) = 0, and fib() = 1;

From the image above we have to mention that:

• The green nodes represent the base cases for our recursion.
• The blue nodes represent the repetitive subproblems that are going to be computed only once when we implement our memoized solution.

The brute force recursive solution for the Fibonacci problem is written below.

Our base case is when num ≤ 2, in this case we will simply return 1 since fib(0) = 0, fib(1)=1 and fib(2) = (fib(1) + fib(0)) = 1.

Until we reach the base case will call the function twice with (num-1) and (num-2) and return the combined result. __ see line 5.

brute force recursion

The previous solution is working fine, but since it has a time complexity of O(2^n) which is terrible for large inputs.

Analyzing brute force recursion complexity:

• The time complexity equals the total number of nodes in the tree or the total number of times we call the Fibonacci function(see the image above).

Since our tree has n levels and each time we move done one level we multiply the number of child nodes by 2 our time complexity will be O(2^n).

• The space complexity: Since in the worst case we will have n function call at the Call Stack (see the left path in the image above for the 7th Fibonacci number) our space complexity will be O(n).

It is time to optimize our solution using memoization.

We have many repeating subproblems ( see the blue nodes in the image above), like the subtree with the root node of number 3 which is repeated 4 times. So we can calculate it only once and cache the value to access it later.

But first, we need a data structure to store our value in, so will choose an object (hash table) since it has O(1) for insertion and lookup. (see line 1 below).

recursive solution (using memoization)

Then we need to add a new base case to test if the result is already in the memo object to return it instead of recomputing it again. (see line 2 above)

And finally, any new values will be stored in the memo object before returning the value. (see lines 10 and 11 above).

Don’t forget to pass the memo object to the function when calling it (in line 10) to share the memo object and make it accessible.

Analyzing Top_down memorization complexity :

• The time complexity: O(n) since each node in the tree will be calculated at least once.
• The space complexity: O(n) remains the same as for the previous solution.

Note:

Any solution for memorization later on in this article will be implemented by following the previous steps.

This is another way to implement memorization.

The solution below is similar to the previous but is implemented using Closures to avoid creating a public variable and polluting our code.

recursive solution (memorization with closures)

Guidelines to follow when using memorization:

1- Implement the Brute force solution (make it work).

And to do it you need to follow these steps:

1. Recursive problems can be visualized as trees so do that.
2. Implement your tree using recursion.

At this point, your solution should be working fine for small input values but it will take quite a long time to resolve for large inputs.

2- Optimize your solution with memorization (make it efficient).

1. Add a memo Object to save our values.

Note: It is worth mentioning that we choose an object (hash table) to store the repetitive values since it has an access time complexity of O(1). But if you choose an array it will work fine.

2. Make sure this object is shared among all recursive calls:

This could be done either by using:

a- Closures. see the recursive solution (brute force).

b- pass it along as an argument by initialing a default empty object at the top of your recursive call and making use of the pass-by-reference characteristics of objects.

3. then add a new base case to check if the value is already in the memo object to return it.

4. and finally we store any unique values into the memo object before returning the value.

It is pretty obvious now that all hard work is done through implementing the brute recursive solution, and that is why it is recommended to do it first before trying to optimize your solution with memoization.

Once you solve some problems and gain some experience you will find yourself implementing the optimized memoization solution directly.

2- Tabulation (iterative, bottom-up approach):

In this approach, we are solving the problem iteratively. we do this by filling a table with the results of the subproblems from the bottom till we reach our final result.

Each value is depending on the previous values in the table either direct or indirect way.

So to solve for any Fibonacci number we will store the values in an array with the first two base cases of fib(0) = 0 and fib(1) = 1.

Then we loop through the array n times starting at the third index (i = 2) which will equal the sum of the previous two indexes.

Once we finished we will have our desired value so we can return it.

iterative solution (using tabulation)

Analyzing bottom_up tabulation complexity :

• The time complexity: O(n) since we are looping through the array n times.
• The space complexity: O(n) since we are storing our values in an array of size n.

Guidelines to follow when using tabulation:

1. Visualize the problem as a table.

2. Define its size related to the inputs.

3. Initialize the table with proper defaults values.

4. Add the base case answers to the table.

5. Loop through the table.

6. Come up with some logic to fill further positions with values related to the current position. (This is the hardest part).

Now it is the fun time we will apply all the knowledge we get so far to solve 3 problems.

Note:

I recommend not to look at the solution directly and implement your solution. If you get stuck reading the explanation then go and look at the final solution.

Examples:

1- Climbing Stairs (See it on LeetCode):

-Using Memoization:

Let's consider finding all the distinct ways to climb 6 step stairs by either climbing 1 step or 2 steps.

The first thing to do is to visualize the problem as a tree data structure.

Tree representing the distinct ways to climb a stair of 6 steps.

Choosing the left node means we are moving 1 step, and choosing the right node means we are moving 2 steps.

From the image above we notice:

• Each parent node is equal to the summation of its direct children's, which is similar to the Fibonacci sequence we previously did.
• The green nodes represent the base cases. If we had 2 steps there are 2 distinct ways to move: either 1 step each time or moving 2 steps directly.
• The blue nodes represent the repetitive subproblems that are going to be memoized.

Next, we need to implement the brute force recursive solution.

from the image above notice when the number of steps n is ≤ 3 the result is simply n. And that will be our base case. (see line 2 below).

Else we will keep calling the function once with (n-1) and other with (n-2) and combine their results.

brute force recursion

Analyzing brute force recursion complexity:

• The time complexity: O(2^n) since we are multiplying the number of nodes by 2 each time we move a level down the tree.
• The space complexity: O(n) since we will have n function calls at the call stack in the worst case.

Optimizing the previous code using memorization should be easier now.

We initialize a memo variable to an empty object. (see line 1 below).

recursive solution (using memoization)

Then we need to add a new base case to test if the result is already in the memo object to return it. (see line 2 above).

And finally, any new values will be stored in the memo object before returning the value. (see lines 10 and 11 above).

Don’t forget to pass the memo object to the function when calling it (in line 10) to share the memo object and make it accessible.

Analyzing Top_down memorization complexity :

• The time complexity: O(n) since each node in the tree will be calculated at least once.
• The space complexity: O(n) remains the same.

-Using Tabulation:

We will choose an array as our table, with the indices representing the number of steps.

Then we will fill it with the base cases results:

• Index [0] represents there are no stairs, so the value for it will be zero.
• Index [1] means there is only one step, so there is only one way to climb it.
• index [2] means there are two steps to climb, and there are also two ways to climb those steps.

memo = [0,1,2, ..... ]

We said previously that the answer to each parent node in the tree equals the summation of the answers of its direct children.

So if we have 3 steps the answer will be memo[2] + memo[1] = 3.

know we need to iterate through the array n times starting from (i = 3) which will equal the sum of the previous two values.

Once we finished we will have our final result at index n.

iterative solution (using tabulation)

Analyzing bottom_up tabulation complexity :

• The time complexity: O(n) since each value will be calculated at least once.
• The space complexity: O(n) remains the same.

2- House Robber (See it on LeetCode):

-Using Memoization:

Consider finding the maximum amount of money that can be made from this array n = [12, 7, 9, 13, 1]. Each value represents the amount of money in a specific house.

Knowing that we can’t rob two adjacent houses let's begin by visualizing the problem as a tree data structure.

Tree representing all the different ways to rob 5 houses to get the max amount possible.

The root node it the tree represent two choices:

• If we decided to rob the first house n[0] = 12, then we can’t rob the second house n[1] = 7, and our next choice will be all the remaining houses except for the second one which results in this subarray [9, 13, 1].
• Or we can skip the first house, so we will have the next 4 houses to choose from [7, 9, 13, 1].

There will be two different ways to choose the house to rob. Our goal is to find the maximum value that we can get.

We will keep repeating the previous two steps as long as we have houses to rob in the subarray.

Once we have no choices (the subarray is empty), then we reach the base case which will return 0.

From the image above we can observe:

• Each parent node represents the maximum value that we can get from the two choices we discussed previously.
• The green node represents the base case which is any empty subarray will return 0. (we draw it only once for simplicity).
• The blue nodes represent the repetitive subproblems that are going to be memoized.

Now it's time to implement the brute force recursive solution.

Our base case will be when we had an empty array representing that we have no houses left to rob, so we can return 0.

Otherwise, we will need to find the max. value between robing either the first house(n[0]) + the remaining houses except for the next one (rob(n.slice(2))) or skip the first house so we have all the remaining houses to choose from (rob(n.slice(1))).( see line 6 below).

brute force recursion

Analyzing brute force recursion complexity:

• The time complexity: O(2^n).
• The space complexity: O(n).

Now it's time for memorization.

First as usual we initialize a memo variable to an empty object. (see line 1 below).

recursive solution (using memoization)

The next step is to add a new base case to verify if the value is already in the memo object or not. (see line 2 above).

The new values will be stored in the memo object before returning the value. (see lines 10 and 11 above).

Analyzing Top_down memorization complexity :

• The time complexity: O(n) since each node in the tree will be calculated at least once.
• The space complexity: O(n) remains the same.

-Using Tabulation:

A one-dimensional array will be a good choice for our table.

Then we will fill it with the base cases results:

• Index [0] represents there are no houses to rob, so the value for it will be zero.
• Index [1] means there is only a single house to rob, so the value here will be the value of the first house at n[0] = 12.

memo = [0,12, ..... ]

Before iterating through the memo to fill it, we need to come up with the logic first.

Here, you may find the logic harder to wrap your head up with than the previous recursive memorize solution. So I advise you to write it down and analyze it.

n = [12, 7, 9, 13, 1]
memo[0] = 0, memo[1] = n[0] = 12         // base cases
memo[2] = max (memo[1], memo[0] + 7)
        = max (12 , 0 + 7)
        = 12   
// basically we are saying which is biger 12 or 7
memo[3] = max (memo[2], memo[1] + 9)
        = max (12, 12 + 9)
        = 21   
// basically we are saying which is biger 12 or 12 + 9
memo[4] = max (memo[3], memo[2] + 13)
        = max (21, 12 + 13)
        = 25
// basically we are saying which is biger 12 + 9 or 12 + 13
memo[5] = max (memo[4], memo[3] + 1)
        = max (25, 21 + 1)
        = 25
// basically we are saying which is biger 12 + 13 or 12 + 9 + 1

So the memo array table values are:

memo = [0, 12, 12, 21, 25, 25]

And our value is at memo[5] = 25;

So we can observe some pattern from the above analysis which is :

memo[i + 1] = Math.max( memo[i], memo[i — 1] + n[i] )

iterative solution (using tabulation)

Analyzing bottom_up tabulation complexity :

• The time complexity: O(n) since each value will be calculated at least once.
• The space complexity: O(n) remains the same.

3- Coin Change (See it on LeetCode):

This problem requires finding all different unique combinations that make up a specific amount of money.

So to solve it, let us consider an amount of 5, and a set of [1, 2, 5] coins.

To avoid repetitive combinations, each time we subtract the total amount by a specific coin we need to remove it from the array of coins (except for the left branch_ see the image below).

Tree structure represents all unique combinations to get an amount of 5 from a set of [1, 2, 5] coins.

Our base cases will be when the amount is equal to 0, which means we got a valid combination of coins that can up the total amount. (see line 6 below).

The other base case is when the total amount is less than 0, which means that the current combination of coins can’t be summed up to make the total amount. (see line 8 below).

To avoid any repetitive combinations we set i = index at line 10.

The result variable will be increased only when the function calls returns 1, indicating a valid combination. (see line 14 below).

Notice that we make use of closures to avoid creating any global variables, and we use an IIFE (Immediately Invoked Function Expression).

Note: This solution can’t be memoized due to the for loop.

recursive solution

Analyzing brute force recursion complexity:

m: amount, n: coins.length.

• The time complexity: O(n^m).
• The space complexity: O(m).

-Using Memoization:

The previous solution has an exponential time complexity which is terrible for large input values.

So we need to come with another optimized solution.

Consider that we have an amount of 2, and a set of [1, 2] coins. We have 2 unique combinations only: either 1 + 1 or 2.

The previous example can be represented by the following tree structure.

Notice how in the left branch we subtract the total amount by the first coin coins[0]. In the right branch, we increase the coins array index by 1, while keeping the amount untouched.

Tree representing all unique combinations to get an amount of 2 from a set of [1, 2] coins.

Now let us consider a total amount of 5, and a set of [1, 2, 5] coins.

Notice how the tree size increased significantly. (open the image in a new tab, or download it to see it better).

Tree structure represents all unique combinations to get an amount of 5 from a set of [1, 2, 5] coins.

Our base cases are:

• When the amount is equal to 0, indicating we have a valid combination. (see line 5 below).
• When the amount is less than 0, indicating the combination is invalid. (see line 6 below).
• When the array of coins is empty, meaning that we have used all the available coins. (see line 7 below).

The optimal substructure for this implementation is at line 9, where we will call the function twice and combine the results.

a recursive solution (using memoization)

Analyzing brute force recursion complexity:

m: amount, n: coins.length.

• The time complexity: O(n*m).
• The space complexity: O(n*m).

-Using Tabulation:

To implement the iterative approach, we need a 2-dimensional array to represent our table.

The size of the table will be memo = [coins.length+1][amount+1] = [4][6] (4 rows and 6 columns). Then the table will be filled by zero’s. (see lines 2 – 4 below).

a table of all unique combinations to get an amount of 5 from a set of [1, 2, 5] coins.

The first column will be filled by 1’s representing our initial values. (see lines 6 and 9 below).

what does each index in the table mean?

lets take the first value to fill which is at i = 1, j = 1.

It means how many unique combinations can we make to get an amount of 1 with a coin set containing only [1]. The answer is 1 combination.

To make it clear let us take another example at i = 3, j= 3.

It means how many unique combinations can we make to get an amount of 3 with a coin set containing only [1, 2, 5]. The answer is 2 combinations (1+1+1, or 1+2).

After we will the table, the only thing remaining is to come up with the logic that connects each value with the other values in the table. (see lines 12-14 below).

My advice is to grab a paper and a pen and try to fill the above table from scratch, to understand the logic better.

iterative solution (using tabulation)

Analyzing brute force recursion complexity:

m: amount, n: coins.length.

• The time complexity: O(n*m).
• The space complexity: O(n*m).

The previous solution can be optimized even better regarding the space complexity to use a 1-dimensional array and get an O(m) space complexity.

The key is we don’t have to keep track of all the values in the table all the time.

Each time we move to fill the next row in the previous table, we need to keep track of the row that is directly above it only.

a 1-D array of all unique combinations to get an amount of 5 from a set of [1, 2, 5] coins.

So at the first iteration, the memo array will be all zeros except for memo[0] = 1.

The second iteration will be at ( i = 1). The third iteration will start at (i = 2). The last iteration will start at ( i = 5).

Notice how in each iteration the green cells are the same as the previous iteration.

iterative solution (using tabulation)

Analyzing brute force recursion complexity:

m: amount, n: coins.length.

• The time complexity: O(n*m).
• The space complexity: O(m).

Conclusion:

To wrap up, dynamic programming can be very intimidating especially for beginners mainly because of the wide variety of problems that it contains.

But through the 3 examples we solved, we found a pattern that can be applied to solve any dynamic programming problem.

In the end, practice makes perfect, so if you want to improve your skills go and give it a shoot in Leetcode or Hacker Rank or any other coding problems website.

Happy coding :)