Lecture 19: Dynamic Programming I: Fibonacci, Shortest Paths
MIT OpenCourseWare4 HN recommenders · recommended in 4 months, 2016–2021
lecture · intro · evergreen · 2016–2021 on HN
Erik Demaine's MIT 6.006 lecture introducing dynamic programming through Fibonacci numbers and shortest paths. It covers memoization, subproblems and optimal substructure.
Recommended as a clear introduction to dynamic programming from a well-regarded instructor.
Up next
3 mo on HNCgroups, namespaces, and beyond: what are containers made from?
Docker
4 HN recommender · 2017–2023
4 mo on HNDr. Satchin Panda on Time-Restricted Feeding and Its Effects on Obesity, Muscle Mass & Heart Health
FoundMyFitness
5 HN recommender · 2017–2018
5 mo on HNClojure Concurrency - Rich Hickey
ClojureTV
5 HN recommender · 2013–2023
10 mo on HNEffective Programs - 10 Years of Clojure - Rich Hickey
ClojureTV
10 HN recommender · 2017–2026
2 mo on HNWhat Makes This Song Great? "Into You" MAX MARTIN
Rick Beato
3 HN recommender · 2020–2022
1 mo on HNLin-Manuel Miranda Performs at the White House Poetry Jam: (8 of 8)
The Obama White House
1 HN recommend · 2016–2024
10 mo on HNCppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”
CppCon
9 HN recommender · 2018–2026
8 mo on HNThe Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?
Reducible
7 HN recommender · 2021–2026
9 mo on HNModern Dictionaries by Raymond Hettinger
SF Python
9 HN recommender · 2016–2025
7 mo on HNCppCon 2014: Chandler Carruth "Efficiency with Algorithms, Performance with Data Structures"
CppCon
7 HN recommender · 2014–2024
7 mo on HNCppCon 2017: Juan Pedro Bolivar Puente “Postmodern immutable data structures”
CppCon
5 HN recommender · 2017–2025
6 mo on HNSorting Algorithms: Speed Is Found In The Minds of People - Andrei Alexandrescu - CppCon 2019
CppCon
7 HN recommender · 2019–2024
4 comments from Hacker News
> on interviews they want you to explicitly construct the array very often i.e. it's the different between hire and a strong hire exactly because @lru_cache is much easier are you serious? someone really asked you to "use array". Beyond stupid if they really did. > you can easily blow the stack for real production grade implementations using recursion recursive solution doesn't automatically mean using a the method stack. you can implement recursive solutions using explicit stack . > dynamic programming proper please. There is no "proper" dynamic programming. Please watch this MIT intro ▶ this video .
I don't think I've ever been asked a DP problem in an interview, and only had to use it while programming once . That said, I liked the MIT lecture on it: ▶ this video
You may also like a couple of lectures by Erik Demaine: Dynamic Programming I: Fibonacci, Shortest Paths ▶ this video Dynamic Programming II: Text Justification, Blackjack link
When you deal with large data sets (e.g. Hadoop/Spark...), BigO starts to hit badly. Dynamic Programming also requires you to have a clue about it. See ▶ this video for some cool explanations.