Lecture 19: Dynamic Programming I: Fibonacci, Shortest Paths

Channel:MIT OpenCourseWare · Length:51:47 · Published:2013-01-14 · Views:2903120

Watch on YouTube

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