Bootcamp

Search…

A.11: Dynamic Programming

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

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.

(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.

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

- 2.
- 1.Note: This can be solved with math and not DP, but please implement the DP version for practice.
- 2.
- 3.

Last modified 2mo ago

Copy link

On this page

Introduction

Introduction Video

Further Reading

Exercises

Part 1

Part 2

Part 3

Part 4