Dynamic programming 101
summary
Shows concrete wins: naive Fibonacci repeats calls so memoization collapses exponential blowup and makes fib feasible; Dijkstra runs with O(n log n) behavior on weighted grids versus greedy or DFS that fail; traveling‑salesman drops from n! brute force to Bellman–Held‑Karp at about n^2·2^n so instances up to ~30 cities become tractable on a laptop; demos convert a grid maze to a graph, writes costs into cells, and measures the actual speedups.
AI-written summary · about
chapters (15)
- 0:00Intro
- 1:01Open source
- 1:51You've got a problem
- 2:34Divide and Conquer
- 2:52Recursion
- 3:35Fibonacci
- 6:55Dynamic programming
- 7:50Graph theory
- 10:08Matrix maze
- 11:00Breadth first
- 11:34Depth first
- 12:23Greedy algorithm
- 13:50Dijkstra's algorithm
- 18:31Time complexity
- 22:37Traveling salesman
related talks
34mKilling Fibonacci
02h 44mMeasure, don’t guess: benchmarking stories from the trenches
14mOptimizing Go code without a blindfold
37mGame of (Developer) Life... Deconstructed
01h 11mMeasuring Performance, JavaScript Games, and Distributed Testing
58mCoverage, quality, and Goodhart's Law
20mWhat's the fuzz all about? Randomized data generation for robust unit testing
31mMaking it Fast: The Power of Benchmarking