Dynamic Programming

20pts

Python

Java

C++

Algorithms

Math

Optimizing recursion using dynamic programming

Note: This article takes a look at a technique that makes recursion much faster. See the recursion article for more context.

Let’s review the Fibonacci sequence. The first two numbers are 0 and 1, and every number after that is the sum of the previous two numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Take a minute to look at this sequence. Say you needed to find a specific value in this sequence - the 89th, for example. How would you use recursion to find that value? Remember a recursive function is a function that calls itself to break down major problems into smaller subproblems, then breaks those subproblems into even smaller subproblems. What would the base case for this recursive function be? The recursive case?

As mentioned above, the first two numbers of this sequence are 0 and 1. This is the base case. Every other number is the sum of the previous two numbers, which can eventually be broken down into the first and second Fibonacci numbers using the recursive case. This code calculates the

n

th Fibonacci number:
Code:

```
def fib(n):
# base case 1
if n == 1:
return 0
# base case 2
if n == 2:
return 1
# recursive case
return fib(n - 1) + fib(n - 2)
# Unit tests to make sure our code is working
print(fib(1))
print(fib(2))
print(fib(3))
print(fib(4))
print(fib(5))
print(fib(6))
print(fib(7))
print(fib(8))
```

Output:
> 0

> 1

> 1

> 2

> 3

> 5

> 8

> 13

> 1

> 1

> 2

> 3

> 5

> 8

> 13

Code:

```
public class FibonacciNumbers {
public static void main(String[] args) {
// Unit tests to make sure our code is working
System.out.println(fib(1));
System.out.println(fib(2));
System.out.println(fib(3));
System.out.println(fib(4));
System.out.println(fib(5));
System.out.println(fib(6));
System.out.println(fib(7));
System.out.println(fib(8));
}
static int fib(int n) {
// base case 1
if(n == 1) {
return 0;
}
// base case 2
if(n == 2) {
return 1;
}
// recursive case
return fib(n - 1) + fib(n - 2);
}
}
```

Output:
> 0

> 1

> 1

> 2

> 3

> 5

> 8

> 13

> 1

> 1

> 2

> 3

> 5

> 8

> 13

Code:

```
#include <iostream>
using namespace std;
int fib(int n) {
// base case 1
if(n == 1) {
return 0;
}
// base case 2
if(n == 2) {
return 1;
}
// recursive case
return fib(n - 1) + fib(n - 2);
}
int main() {
// Unit tests to make sure our code is working
cout << fib(1) << "\n";
cout << fib(2) << "\n";
cout << fib(3) << "\n";
cout << fib(4) << "\n";
cout << fib(5) << "\n";
cout << fib(6) << "\n";
cout << fib(7) << "\n";
cout << fib(8) << "\n";
return 0;
}
```

Output:
> 0

> 1

> 1

> 2

> 3

> 5

> 8

> 13

> 1

> 1

> 2

> 3

> 5

> 8

> 13

Notice that when you call

fib(n)

, the function needs to find the values of fib(n-1)

and fib(n-2)

. Solving for these smaller fibonacci numbers are subproblems — they are smaller problems that need to be solved in order to solve the whole problem.
Here is the issue: if you want to calculate a very large Fibonacci number (for example, the 100th Fibonacci number) it takes ages. Look at how calculating

fib(6)

runs:
As you can see, just calling this function for a number as small as 6 takes 15 calculations. It gets ugly very quickly with higher numbers. But take a closer look. Are there some calls to *It would be easier to just call * You wouldn’t have to re-evaluate that subproblem again for that Fibonacci number no matter how many times it comes up!

fib()

that are identical? fib(4)

is called twice, and each time it calls fib(3)

and fib(2)

. Then, each fib(3)

calls fib(2)

and fib(1)

. That’s a lot of repetitive calls! fib(4)

once, and then save that number to use later because it never changes.
This technique of storing the solutions to subproblems that are repeatedly solved is called **dynamic programming**. Dynamic programming is a powerful technique that has applications for a wide variety of problems. For instance, think of a shortest path algorithm— what is the best way to get from A to B? Well, if it is possible to find the best way to just get from A to some point in between, we can treat it as a sub-problem to evaluate, turning this daunting problem into smaller steps.

There are two requirements that need to be fulfilled in order to apply dynamic programming to a problem:

**Overlapping subproblems**- there are (1) subproblems and (2) the solutions to some (or all) of the subproblems need to be used more than once**Optimal substructure**- the larger problem can be broken down into subproblems.

Let’s modify the

fib()

function to apply dynamic programming in 3 steps:
- Create an array called dpto store the solutions to our subproblems when we calculate them. In this array,dp[x]is equivalent to the output offib(x).
- Add another base case that checks if we’ve already solved a subproblem and return the previously-calculated solution if we’ve already solved it.
- Add code to the recursive case that stores solved subproblems into dp.

Code:

```
dp = [0] * 10000
def fib(n):
# base case - subproblem we’ve already solved
if dp[n] != 0:
return dp[n]
# base case - fib(1)
if n == 1:
return 0
# base case - fib(2)
if n == 2:
return 1
# recursive case
dp[n] = fib(n - 1) + fib(n - 2)
return dp[n]
# Unit tests to make sure our code is working
print(fib(1))
print(fib(2))
print(fib(3))
print(fib(40))
```

Output:
> 0

> 1

> 1

> 63245986

> 1

> 1

> 63245986

Code:

```
public class FibonacciNumbers {
public static void main(String[] args) {
// Unit tests to make sure our code is working
System.out.println(fib(1));
System.out.println(fib(2));
System.out.println(fib(3));
System.out.println(fib(40));
}
static int[] dp = new int[10000];
static int fib(int n) {
// base case - subproblem we’ve already solved
if(dp[n] != 0) {
return dp[n];
}
// base case - fib(1)
if(n == 1) {
return 0;
}
// base case - fib(2)
if(n == 2) {
return 1;
}
// recursive case
dp[n] = fib(n - 1) + fib(n - 2);
return dp[n];
}
}
```

Output:
> 0

> 1

> 1

> 63245986

> 1

> 1

> 63245986

Code:

```
#include <iostream>
using namespace std;
int dp[10000] = {};
int fib(int n) {
// base case - subproblem we’ve already solved
if(dp[n] != 0) {
return dp[n];
}
// base case - fib(1)
if(n == 1) {
return 0;
}
// base case - fib(2)
if(n == 2) {
return 1;
}
// recursive case
dp[n] = fib(n - 1) + fib(n - 2);
return dp[n];
}
int main() {
// Unit tests to make sure our code is working
cout << fib(1) << "\n";
cout << fib(2) << "\n";
cout << fib(3) << "\n";
cout << fib(40) << "\n";
return 0;
}
```

Output:
> 0

> 1

> 1

> 63245986

> 1

> 1

> 63245986

Dynamic programming is a powerful optimization technique that can greatly reduce recursion runtimes. While we’ve only seen one example with fibonacci numbers in this article, there are many other applications for dynamic programming and we encourage everyone to continue learning about it (e.g., Dijkstra's algorithm, Tower of Hanoi, egg drop puzzle, matrix multiplication)!

You can play with all the code we've used in this article on Replit:

Join our discord server for updates, announcements, future event planning, to ask questions, or just for fun!

Copyright ©2021 Howard County Hour of Code

Copyright ©2021 Howard County Hour of Code