Bootcamp
Search…
A.11: Dynamic Programming

# Introduction

Dynamic programming allows us to optimise recursive solutions by "caching" intermediate calculation results to reduce repeated and redundant calculations.

### Why is it called Dynamic Programming?

According to Wikipedia, "The word dynamic was chosen [...] to capture the time-varying aspect of the problems, and because it sounded impressive. The word programming referred to the use of the method to find an optimal program, in the sense of a military schedule for training or logistics." In other words, the name makes this algorithm topic seem harder and more esoteric than it is.

## Introduction Video

(the first 40 minutes are the basic definition of Dynamic Programming- no need to watch 5 hours!!)
Calculating the nth fibonacci number using dynamic programming.
fib_table = {} # table to store previously computed values
def fib(n):
if n < 2:
return n
if n in fib_table:
# give back a previously calculated result
return fib_table[n]
result = fib(n-1) + fib(n-2)
# store a result that has been calculated
fib_table[n] = result
return result

What is Dynamic Programming? - Grokking Dynamic Programming Patterns for Coding Interviews
Educative: Interactive Courses for Software Developers
Some dynamic programming problems can be expressed in a table.

# Exercises

Please fork starter code Repls and attempt solutions there. Feel free to compare with reference solutions after attempting each problem. Have fun!

## Part 4

1. 2.
1. 1.
Note: This can be solved with math and not DP, but please implement the DP version for practice.
2. 2.
Rocket Academy solution code: https://pastebin.com/mywskXkk
3. 3.
Rocket Academy solution video: https://youtu.be/SUGb21Ec5kE?t=2113 (35:13 until about 1:48:30)