Lecture 19: Dynamic Programming I: Fibonacci, Shortest Paths
Channel:MIT OpenCourseWare · Length:51:47 · Published:2013-01-14 · Views:2903120
Summary
Erik Demaine's MIT 6.006 lecture introducing dynamic programming through Fibonacci numbers and shortest paths. It covers memoization, subproblems and optimal substructure.
Why HN recommends it
Recommended as a clear introduction to dynamic programming from a well-regarded instructor.
Please watch this MIT intro — HN, 2021
Algorithms & data structures · University lectures & courses
Subtitles (excerpt)
The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu. PROFESSOR: We're going to start a brand new, exciting topic, dynamic programming. AUDIENCE: Yes! PROFESSOR: Yeah! So exciting. Actually, I am really excited because dynamic programming is my favorite thing in the world, in algorithms. And it's going to be the next four lectures, it's so exciting. It has lots of different facets. It's a very general, powerful design technique. We don't talk a lot about algorithm design in this class, but dynamic programming is one that's so important. And also takes a little while to settle in. We like to inject it into you now, in 006. So in general, our motivation is designing new algorithms and dynamic programming, also called DP, is a great way-- or a very general, powerful way to do this. It's especially good, and intended for, optimization problems, things like shortest paths. You want to find the best way to do something. Shortest path is you want to find the shortest path, the minimum-length path.
On 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… — dominotw, 2021-04
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: [VIDEO] — dehrmann, 2021-02
You may also like a couple of lectures by Erik Demaine: Dynamic Programming I: Fibonacci, Shortest Paths [VIDEO] Dynamic Programming II: Text Justification, Blackjack [LINK] — gbacon, 2019-04
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 [VIDEO] for some cool explanations. — philippeback, 2016-08
Related videos
- Cgroups, namespaces, and beyond: what are containers made from? · Docker · 54:24
- Dr. Satchin Panda on Time-Restricted Feeding and Its Effects on Obesity, Muscle Mass & Heart Health · FoundMyFitness · 1:31:34
- Clojure Concurrency - Rich Hickey · ClojureTV · 2:32:38
- Effective Programs - 10 Years of Clojure - Rich Hickey · ClojureTV · 1:14:51
- What Makes This Song Great? "Into You" MAX MARTIN · Rick Beato · 30:12
- Lin-Manuel Miranda Performs at the White House Poetry Jam: (8 of 8) · The Obama White House · 4:27
- How to Speak · MIT OpenCourseWare · 1:03:42
- 1. Introduction to Human Behavioral Biology · Stanford · 57:14
- LEADERSHIP LAB: The Craft of Writing Effectively · UChicago Social Sciences · 1:21:51
- MIT's Pathway to Fusion Energy (IAP 2017) - Zach Hartwig · MIT Plasma Science and Fusion Center · 1:11:39
- Stanford's Sapolsky On Depression in U.S. (Full Lecture) · Stanford · 52:28
- Justice: What's The Right Thing To Do? Episode 01 "THE MORAL SIDE OF MURDER" · Harvard University · 54:56
- Lec 1 | MIT 18.06 Linear Algebra, Spring 2005 · MIT OpenCourseWare · 39:49
- Randy Pausch's Last Lecture: Achieving Your Childhood Dreams · Carnegie Mellon University · 1:16:27
- Lecture 1A: Overview and Introduction to Lisp · MIT OpenCourseWare · 1:12:55
- Lecture 1A | MIT 6.001 Structure and Interpretation, 1986 · MIT OpenCourseWare · 1:12:55