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

Further Reading

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 1

Part 2

Part 3

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)
Copy link
On this page
Introduction
Introduction Video
Further Reading
Exercises
Part 1
Part 2
Part 3
Part 4