Dynamic Programming (Think Like a Programmer)

This video is about a cool technique which can dramatically improve the efficiency of certain kinds of recursive solutions. It's called "dynamic programming." The name isn't very helpful, but as you'll see, it's easy to implement once you understand the basic idea.

Your comments and suggestions for future videos are welcome.

"Think Like a Programmer" is a book I've written to help programmers with problem solving. If you've found that you are able to read programs and understand programming language syntax but aren't always confident writing programs from scratch, my book can help.

For more information on the book head to one of these:

Connect with me:

[Jeff-rrzi]

Great video. Your analogies and upbeat style make it engaging. There are too many dynamic programming videos on youtube that focus on just the “how-to”. Understanding the problem…and understanding the “why?” of the steps are important. Thank you. I hope you might consider a part 2 for this video, covering the iterative bottom-up dynamic programming approach.

[blingbam]

You mispoke a few times when describing the table in the first problem. @1:51 . I think you meant "... and the number of workers on blocks 3-6"

[taritgoswami]

Thanks, it was a nice explanation. Can you discuss some graph related problems with examples?

[sharan]

Isnt using a map or dictionary or hash data structure to store better than using an array?

[hasiqi]

This seems a memoized solution, not a DP solution

[mind-matter-kashishgupta]

I don't understand the matrix table ?
What is in coloum and what is in row ?
Also in coloum there are two nummbering, why is this so?

[DunderDawg]

This is a very good video, V.


Going through a couple of online resources, like Geeks for Geeks, almost every single one discusses how to identify DP problems and it always comes down to: 1. optimal substructure (which took me a long time to understand), and 2. overlapping subproblems.

The overlapping subproblems condition is easy to understand, but it took me a long time to grok what an "optimal substructure" was, but also what recursive problems don't yield an optimal substructure (longest path problem). To my understanding (correct me if I'm wrong), an optimal substructure is exhibited when the subproblems are "additive" in a manner that provides us the answer to the primary problem as long as the optimal solution can be constructed efficiently from optimal solutions of its subproblems. I think the link of the gist that I've provided really puts this on display in the last version of the fib function (as we can just add values already tabulated).

[thesuperiorman]

It's actually about size because the bigger the size is, the more likely you are to get caught. That is why thieves most prefer to steal small precious items.

[sumeshprabhune]

Your knapsack code is recursion + memoization; and not dynamic programming. A dynamic programming code wouldn't recursively call itself ever.

[suniljadhav]

Lol the excel made it complicated than what it was suppose to be.