Skip to content
Hallway
0:00 / 0:00

#dynamicprogramming#memoization#fibonacci

Lecture 19: Dynamic Programming I: Fibonacci, Shortest Paths

MIT OpenCourseWare

6.5M subscribers • 34 videos on Hallway • University channel

YouTube
  • Recommended by 4 people: 4 on Hacker News.
  • A classic. People kept recommending it from 2016 to 2021.
  • Presented by Erik Demaine, Professor of Computer Science at MIT

Intermediate. Assumes working knowledge.

2.9M views13 years ago4 recommendations

Computer scienceAlgorithmsData structures

Erik Demaine introduces dynamic programming, explaining memoization, subproblems, and shortest paths using Fibonacci numbers as a starting example.

MIT 6.006 Introduction to Algorithms, Fall 2011 View the complete course: ocw.mit.edu/6-006F11 Instructor: Erik Demaine License: Creative Commons BY-NC-SA More information at ocw.mit.edu/terms More courses at ocw.mit.edu

Why it's here

4 people recommend this

What people say. Highly recommended as one of the clearest and most intuitive lectures for learning dynamic programming.

Moments people linked to

philippebackon Hacker News • Recommends

On “The Imposter's Handbook”

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 link to this video for some cool explanations.
View on Hacker News

gbaconon Hacker News • Recommends

On “Graphical Introduction to Dynamic Programming”

You may also like a couple of lectures by Erik Demaine: Dynamic Programming I: Fibonacci, Shortest Paths link to this video Dynamic Programming II: Text Justification, Blackjack link
View on Hacker News

dehrmannon Hacker News • Recommends

On “Algorithms by Jeff Erickson”

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: link to this video
View on Hacker News

dominotwon Hacker News • Recommends

On “Dynamic Programming vs. Divide-and-Conquer (2018)”

> 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 link to this video .
View on Hacker News

Dexterson Stack Overflow • Mentions

…e useful. for example consider this below graph. A->B B->C C->A I saw a solution in an MIT lecture but the lecture skimmed over it with reference to something taught earlier and couldn't catch it. In short it kind of replicates the nodes in layers in a way that the end graph denotes a DAG but conveys the same path information. See 46:59 link to this video Edit : There is an explanation of turning cyclic graphs into dags in this MIT recitation at 36:57 link to this video Se also Wikipedia : cycle and forest Edit: I want to apply dynamic programming over a problem which is a cyclic graph e.g) say shortest path problem Delta(S,D) wh……
9View the answer

Suneelon Computer Science Stack Exchange • Mentions

I was watching a dynamic programming video by Erik Demaine . He says here link to this video , finding the shortest paths from S to V for all V, by guessing the node after the starting node is not the right approach, and instead should guess the node before the last node. I didn't understand his explanation. Can someone explain better why find the path backwards? It seems to me that you should get the same answer either way and both approaches are equally good.
0View the answer