Dynamic programming - 101

on YouTube ↗40m

" summary

Explains how memoization turns exponential Fibonacci recursion into near-linear code, cutting redundant calls by about 99% for fib(500); demonstrates breadth‑first and depth‑first search, then Dijkstra for guaranteed shortest paths while typically exploring far less than the whole graph; lays out Bellman‑Held‑Karp for TSP at O(n^2 2^n), noting it reaches about 35 cities on a laptop and contrasts that with factorial blowup (15! = 1.3 trillion); points out Composer’s SAT work and that Neo4j embeds these algorithms.

AI-written summary · about

" chapters (18)

1. 0:00Start
2. 0:09Dynamic Programming 101
3. 0:35Basics of Dynamic Programming
4. 3:56Recursion
5. 9:11Graph Theory
6. 11:05Search Algorithms
7. 12:33Find a Path with the Least Number of Nodes
8. 12:48Breadth-First Search
9. 15:44Depth First Search
10. 18:15Dijkstra Algorithm
11. 24:14Time Complexity
12. 25:22Find the Shortest Path
13. 27:28Traveling Salesman Is the Tsp Problem
14. 31:02Integer Factorization Problem
15. 35:35The Bellman Held Cult Algorithm
16. 37:07Why Is Called Dynamic Programming
17. 39:17The Benefits of an Indexed Database Compared to a Graph Database
18. 39:35Graph Database

" related talks

• 37mDynamic programming at ease - with Grammars, Algebras, ProductsStefanie Schirmer · Strange Loop 2014
• 34mAlgorithms to liveElle Meredith · Keep Ruby Weird 2017
• 54mAmazing Algorithms for Solving Problems in SoftwareBarry Stahl · NDC Oslo 2022
• 09mOuvroir de Code PotentielAnders Norås · NDC Copenhagen 2025
• 15mComputational Mobility: Learning, Prediction, and AlgorithmsSreenivas Gollapudi · Eighth Annual Industry Day
• 29mTed Willke, Senior Principal Engineer & GM, Datacenter Group, IntelTed Willke · MLconf SF 2014
• 46mCorecursion, Codata, and Just a Little Combinatorial Game TheoryCarlos Rodrigues · LambdaConf 2017
• 01h 12mA Brief Introduction to Algorithms, Game Theory and Risk-Averse Decision MakingEvdokia Nikolova · Real-Time Decision Making Boot Camp, Spring 2018