Opening Dynamic Programming: Dance Dance Revolution (MIT 6.006 Recitation 22)
Dynamic Programming: Dance Dance Revolution (MIT 6.006 Recitation 22)
- Length
- 53 min
- Level
- Undergraduate
- Recorded
- MIT2013
Chapter 1 of 8: Before the lecture
The Dance Dance Revolution problem models the game as an algorithmic path-finding challenge to minimize total physical effort or maximize score. The lecture constructs a state representation using the current note index and the positions of both feet, while introducing blank intermediate states to account for necessary foot recentering. Edges between states are weighted by a delta function measuring move difficulty. The resulting structure forms a directed acyclic graph, which allows the optimal sequence of moves to be computed using shortest path algorithms.

Your comment is kept while you sign up.Sign in
Applies dynamic programming and graph shortest path algorithms to model and solve the Dance Dance Revolution game.
The Dance Dance Revolution problem models the game as an algorithmic path-finding challenge to minimize total physical effort or maximize score. The lecture constructs a state representation using the current note index and the positions of both feet, while introducing blank intermediate states to account for necessary foot recentering. Edges between states are weighted by a delta function measuring move difficulty. The resulting structure forms a directed acyclic graph, which allows the optimal sequence of moves to be computed using shortest path algorithms.
This lecture
Lecture 31 of 31 of Introduction to Algorithms.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.