Dynamic Programming: Bottom-Up

Previously I talked about using recursion and memoization top-down approach to solving recursive problems(specifically the Fibonacci Sequence). This week I want to go over dynamic programming using an iterative bottom-up approach.

In the Fibonacci sequence a number in the sequence is equal to the previous two numbers in the sequence. n = (n-1) + (n- 2)

The recursive way would solve f(n) = f(n-1 ) + f(n -2) over and over even it it’s solved f(n). In the memoization way, it would check if f(n) was already solved and use that answer. In the bottom up approach, we will solve f(0) (the bottom) to f(n) iteratively.

Image for post
Image for post
bottom-up iterative approach

First we’ll create an array (dp) based on the size of n. If we are trying to solve fib(6) dp = Array.new(n+1, 0) will create an array of [0,0,0,0,0,0,0].

We will also declare our base case. We know that the 0 and 1st numbers in Fibonacci will always be 0 and 1 respectively.

Image for post
Image for post

We then move onto our for loop. Since we already know our base case of 0 and 1, we’ll start our loop at 2 until we hit the end.

When i = 2. dp[2] = dp[i -1] + dp[i -2] (dp[1] + dp[0]).

0 + 1 = 1 (dp[2] = 1)

Image for post
Image for post

dp[3] = dp[2] + dp[1] which is 2.

We’re just summing the previous 2 values (dp[i-1] + dp[i2])

Image for post
Image for post

We’ll keep doing this until i reaches 6.

Image for post
Image for post

When we return the function, we return dp[n] which in this case is dp[6]. The 6th position of the Fibonacci sequence is 8.

When using a dp table, we want the last item in the table, which in this case is 8.

A more complex case for using a DP Bottom-Up approach

A popular code challenge question that pops up is the coin change problem.

Given a value (n), and an array of coins of different values (k), how many possible ways are there to make N.

exampleN = 10 (our target value)K = [1, 5, 10] (our array of coins)There are 4 different ways to make 10 cents.

Our DP table

Image for post
Image for post

when K is 0 our options for coins are 0 (none) and 1. When the target is 0 using 0 coins we can have 1 possible way of making 0 (0 coins). When the target is 1, there is 1 possible way using 1 1cent coin. When the target is 2, there is 1 possible way using 1 + 1 cent coins. This goes all the way to 10.

So if we have an array of [[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0]]. We know that index 0, is 1 for every since one.

[[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0]]

Image for post
Image for post

We can also say, that using 0 coins, we can always have 1 way to make 0.

Image for post
Image for post
our base case would be
[[1,1,1],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0]]

Now, lets look at 5. Using a set of coins, 0,1, and 5. We can’t make a target of 1 using 5. 5 doesn’t going into 1.

Image for post
Image for post
red boxes are solved. solid blue box is the 5 into 1, which is 0.

But, we know that in a set of 1 and 5, there is 1 possible way to reach a target of 1. this is represented as k-1 (for now)

Image for post
Image for post
k-1 is 1 (circled)

So, dp[n][k] is equal to dp[n][k] + dp[n][k-1]. Using that logic, we can at least fill in the table to dp[4].

When we reach dp[5], k(5) goes into n(5) once! So we can say, we can hit the target of 5 using 1 5 cent coin. We also know, we can a target of 5 using 5 1 cent coins. There’s 2 possible ways.

dp[n][k] = (dp[n] / dp[k]) + dp[n][k-1]
Image for post
Image for post
using the coin itself(dark blue) and using the previous coins possible solutions

So, 1 + 1 = 2

Image for post
Image for post

When we reach n = 10, k(5) goes into 10 twice. plus the previous solution for 1, we get 2 + 1 = 3

Image for post
Image for post

Using the formula, dp[n][k] = (dp[n] / dp[k]) + dp[n][k-1], the bottom row excluding the last box would look like the following.

Image for post
Image for post

We can see 10 goes into 10 once. Adding dp[n][k-1](3) we get 4.

Image for post
Image for post

Our expected output should be 4.

Putting it together

First we need to setup our array. Our array should be the length of n + 1 (dont forget arrays start at 0 and we need index of n)

Image for post
Image for post

If you recall our base case, every dp[n][0] is 1 and k for dp[0][k] is 1, we can set this up by doing the following.

Image for post
Image for post
setting up our base case is complete

Now, onto the next part

We want to iterate through every target of n to figure out how many possible combinations of coins (k) to reach n.

Image for post
Image for post

The formula we came up with was dp[n][k] = (dp[n] / dp[k]) + dp[n][k-1]

Using our i and j loops we can write this as:

dp[i][j] = (i / k[j]) + dp[i][j-1]since i represents n and k[j] represents the current coin
Image for post
Image for post

If we compare output to our dp table, we can see it matches up.

Image for post
Image for post

Since we want to return the last box(4) (the 4 possible ways to get N using K coins) We need to return the last index of the last inner array. We can do this by using

return dp[-1][-1] 
# -1 get the last item of the array.
# dp[-1] is [1,3,4]
# dp[-1][-1] is 4
Image for post
Image for post
using dp[-1][-1] we can target the last “box” which is 4

Bottom up can be a bit confusing and hard to wrap your ahead around it, but with more practice you’ll get used to it.

Fullstack Software Engineer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store