Bootcamp
Search…
📅
Course Schedule
0: Language and Tooling Teaching Guide
1: Frontend Basics Teaching Guide
2: Backend Basics Teaching Guide
3: Backend Applications Teaching Guide
4: Backend Structure Teaching Guide
5: Full-Stack Applications Teaching Guide
6: Frontend Infrastructure Teaching Guide
7: React Teaching Guide
8: Advanced React Teaching Guide
9: Advanced Topics Teaching Guide
🧮
Algorithms Teaching Guide
💼
Interview Prep Teaching Guide
☺
User Experience Teaching Guide
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.
1
fib_table = {} # table to store previously computed values
2
​
3
def fib(n):
4
if n < 2:
5
return n
6
if n in fib_table:
7
# give back a previously calculated result
8
return fib_table[n]
9
10
result = fib(n-1) + fib(n-2)
11
12
# store a result that has been calculated
13
fib_table[n] = result
14
15
return result
Copied!

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

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)
Last modified 1mo ago