Dynamic Programming

• You probably won't see any dynamic programming problems in your interview, but it's worth being able to recognize a problem as being a candidate for dynamic programming.

• This subject can be pretty difficult, as each DP soluble problem must be defined as a recursion relation, and coming up with it can be tricky.

• I suggest looking at many examples of DP problems until you have a solid understanding of the pattern involved.

• The Skiena videos can be hard to follow since he sometimes uses the whiteboard, which is too small to see

• Lecture 19 - Introduction to Dynamic Programming - Skiena CSE373 (video)

• Lecture 20 - Edit Distance - Skiena CSE373 (video)

• Lecture 20 - Edit Distance (continued) - Skiena CSE373 (video)

• Lecture 21 - Dynamic Programming - Skiena CSE373 (video)

• Lecture 21 - Dynamic Programming and Review - Skiena CSE373 (video)

• Dynamic Programming 0 (starts at 59:18) - Simonson (video)

• Dynamic Programming 1 - Lecture 11 - Simonson (video)

• Dynamic programming 2 - Lecture 12 - Simonson (video)

• Dynamic Programming Problems - Youtube (videos)

• Dynamic Programming - Yale (article)

• The RNA secondary structure problem - Coursera (video)

• A dynamic programming algorithm - Coursera (video)

• Illustrating the DP algorithm - Coursera (video)

• Running time of the DP algorithm - Coursera (video)

• DP vs. recursive implementation - Coursera (video)

• Global pairwise sequence alignment - Coursera (video)

• Local pairwise sequence alignment - Coursera (video)

More Content

• DP I: Fibonacci, Shortest Paths - MIT 6.006 (video)
• DP II: Text Justification, Blackjack - MIT 6.006 (video)
• DP III: Parenthesization, Edit Distance, Knapsack - MIT 6.006 (video)
• DP IV: Guitar Fingering, Tetris, Super Mario Bros. - MIT 6.006 (video)
• Dynamic Programming & Advanced DP - MIT 6.046 (video)
• Dynamic Programming: All-Pairs Shortest Paths - MIT 6.046 (video)
• Dynamic Programming (student recitation) - MIT 6.046 (video)