Introduction to Dynamic Programming: Fibonacci Numbers

This video fixes a typo from the previous upload (an index i vs. n in the iterative versions of the algorithm). Otherwise it is the same content.

Table of Contents:

00:00 - Introduction
00:20 - Fibonacci Sequence Definition
00:35 - Fibonacci Algorithm
00:45 - Recursion Tree
02:04 - Memoized Algorithm
02:26 - Pruned Tree
03:47 - Second View
05:08 - Table Fill Order
05:42 - Iterating to Eliminate Recursion
06:49, 7:12 - Optimizing Space
07:49 - Dynamic Programming Template
08:44 - Up Next

[IrmaModzgvrishvili]

If you're looking to truly grasp the concept, this is probably the best video out there, and it does so in a very short amount of time.

[srinivasnangunuri]

This is Gold. Every programmer must watch this to understand Dynamic Programming at its core. to understand the foundations well, decipher the nuts and bolts that makes a DP problem usually difficult to solve. This illustration makes it easier to break down and lay out proper baby steps to approach any complex DP problem. Great job Mr.Taylor!

[Anonymous_Wolfie]

It's such a weird experience to have my professor whispering in my ears

[eug]

I would apply to SJSU and pay a full year of tuition just to be blessed by your hair 😍

[infodemicyar]

I LOVE you, they do have quite the attitude..

[bablobko]

One doubt I have, they all say that Fibonacci is a good starting example of Dynamic programming, and as we know that the prerequisite for DP is that the problem should have optimal substructure and overlapping subproblems.
Overlapping subproblems is very much evident in Fibonacci but how can we say that it has optimal substructure?

By optimal substructure I understand we mean that the "optimal solution of the original problem is composed of optimal solutions of the subproblems".