Dynamic Programming

Video

Table of Contents

• 1:09 - Recurrences
• 2:38 - Fibonacci Sequence
  • 4:49 - Recursive code (using the recurrence directly)
  • 5:16 - Issue with this method
• 9:15 - Remembering what we’ve already done (memoization)
  • 13:09 - Optimization by ‘forgetting’ what we don’t need anymore
• 17:10 - Recap on dynamic programming
• 20:15 - Example: Change-making
  • 20:19 - Problem definition
  • 22:11 - The dynamic programming trick
  • 27:55 - Formalizing the argument
  • 35:48 - Complexity analysis
    • 38:15 - Being more precise with complexity

Extended Notes

Code used for getting $n^{\text{th}}$ Fibonacci number using the different methods:

Code to solve Change-Making (second example)