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:
Amazon page for the book: amzn.to/1MZlmlY
My site: www.vantonsprau...
My publisher's site: nostarch.com/th...
Connect with me:
My site: vantonspraul.com
Twitter: / vantonspraul
Facebook: / thinklikeaprog

[@Sahilbc-wj8qk]

Each concept is explained with Patience + Use of easy words. Amazing . Well I am still amazed that how Dp can optimize the problems...

[@Happy-ns1ij]

DP is used when if using recursion, same values are being calculated lot of times. Instead of calculating values everytime, we just store them and use it when required.

[@moosegoose1282]

Omg it’s English pray the gods

[@alimomeni4777]

praise* ironic isn't

[@N4ppzter]

@@alimomeni4777 *it

[@mortkebab2849]

@@alimomeni4777 Yes, it isn't ironic.

[@shanugarg8428]

If you don't know, why we use dynamic programming then whatever you understand related to that is junk! If you catch this, checkout : kzbin.info/www/bejne/rYWylamee9yhpbM

[@Jeff-rr7zi]

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.

[@vantonspraul]

Thank you! That's pretty much my philosophy to teaching in general. So many ideas are presented as a kind of recipe to follow, without understanding how the recipe works. You can't really use something you don't understand. That's a good idea for a bottom-up dynamic programming video. I considered including that in this one but it was already getting long, plus I've been meaning to do a video about converting recursion to iteration, and those subject dovetail nicely. I'll see if I can whip it up soon.

[@blingbam404]

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"

[@sharan9993]

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

[@CodingJesus]

Amazing explanation.

[@taritgoswami3957]

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

[@leandrormor]

thanks a lot, making dp easer!

[@Fr3ddieNicholson]

This is really helpful. Thanks

[@Btc2Nex]

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?

[@vantonspraul]

You mean the spreadsheet I show at 1:34 or so? The tan-colored labels across the top (A through I) and down the whole left side (1 to 17) are how Excel (the spreadsheet application I'm using) identifies each cell; you can ignore those labels for this video. Instead, focus on the orange column labelled 1-8 and the yellow row marked 1-8. Each of the white cells in the upper diagonal can be used to store the number of potential customers in a range of blocks on Main Street. The numbers in the column of orange cells indicates the first block number in the range and the numbers in the row of yellow cells indicates the last block number in the range. So at 1:34 in the video, the 23 is to the right of the orange 1 and below the yellow 3. So this indicates the range of 1-3; that is, there are 23 people working total on blocks 1 through 3.

[@Btc2Nex]

V. Anton Spraul If 45 is total number of workers from 4-6 then it should lie in 4(orange ) and 6 (yellow). Right ?

[@vantonspraul]

That's it! Sorry for any confusion.

[@shreyashjoshi4188]

Good explanation.

[@techsavvy1457]

Your channel is a gold mine!

[@vantonspraul]

Thanks! I'm glad you are finding them helpful.

[@codethings271]

Great content keep it up:)

[@vantonspraul]

Thanks! More on the way...

[@notDiru]

5:04 error CS1026: ) expected.

[@mingjiang8971]

This seems a memoized solution, not a DP solution

[@vantonspraul]

This is memoization, but memoization as done here is a form of dynamic programming.

[@thesuperiorman8342]

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.

[@vantonspraul]

Hmm. I never pictured this as a shoplifting, more like a dude breaking in at night with a swag bag.

[@wulymammoth]

This is a very good video, V. Any chance that you can expand upon this video by adding details about memoization versus tabulation in DP? I think there's a real distinction that needs to be made here -- producing the Fibonacci sequence can be done in recursion, recursion with memoization (DP), and an iterative solution (DP). I've got a gist here: gist.github.com/sudostack/7a703de4c91f62e2137e0603ad893a78. One thing to note is DP oftentimes utilizes tabulation with an n-dimensional array/matrix that corresponds with n-changing params (not constant function parameters). 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).

[@kunal_chand]

Awesome !!!!!!!!!!!!!!!!!!!!!

[@vantonspraul]

Thanks, I appreciate the support!

[@philmourelle]

beautiful

[@vantonspraul]

Thank you!

[@sumeshprabhune12]

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

[@vantonspraul]

Memoization is a form of dynamic programming. In fact, it is synonymous with top-down dynamic programming. You may have encountered someone who uses dynamic programming only to refer to bottom-up dynamic programming, which avoids recursion altogether, but that usage is not standard. I've seen posts on Stack Exchange, for example, make this distinction, but it is artificial. Either version avoids computing a function with the same parameters more than once.

[@suniljadhav4383]

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

[@ariabanazadeh1016]

easy problems not usefull