Mastering Dynamic Programming - How to solve any interview problem (Part 1)

Mastering Dynamic Programming - How to solve any interview problem (Part 1)

Tech With Nikola

11 месяцев назад

662,317 Просмотров

Ссылки и html тэги не поддерживаются


Комментарии:

fireinthehole
fireinthehole - 16.11.2023 01:25

YOU ARE AMAZING THANK YOU

Ответить
Левченко Єгор
Левченко Єгор - 14.11.2023 21:32

I don't know how, but your video came across as timely as ever!
I am a student and I was given a recursion problem. It may not have been necessary, but I'm sure glad that I was able to optimize recursion (which is so much slower than the iterative approach that already for the 50th element you have to wait more than 30 seconds, when the iterative approach manages in less than a second)

Ответить
Tyler Perlman
Tyler Perlman - 13.11.2023 10:36

As other people have mentioned, for some of the questions, there are ways to do direct mathematical computations without the use of Dynamic Programming, and I thought I would share such a method for the "How Many Ways?" coins problem. Specifically, I will utilize combinatorics (generating functions).

One caveat: This method does not distinguish between the order in which the coins are picked. That being said, there would also be ways (albeit slightly more complicated) to do that with combinatorics as well.

This is the problem of counting the number of partitions of a number n into "parts" of only certain sizes. If we say that the only sizes we allow (the values of each coin) are the elements a in some set A = {a1, a2, ... }, then the solution to this problem will be given by the coefficient in front of the x^n term of the power series expansion of the function:

f(x) = product over all a in A of 1/(1-x^a) . This is equivalent to (1 + x^a1 + x^(2*a1) + ....)*.....*(1 + x^ak + x^2*ak + .....) where we can drop any terms where the power of x exceeds n.

So, for example, in the case of coins of sizes 1, 4, and 5:
A = {1, 4, 5}; n = 13
f(x) = 1/((1-x)(1-x^4)(1-x^5)) = (1+x+x^2+x^3+...+x^13)*(1+x^4+x^8+x^12)*(1+x^5+x^10) = 1 + x + x^2 + x^3 + 2*x^4 + ... + 16*x^20 + ....

This tells us that there are 16 distinct ways of partitioning 20 cents into coins of sizes 1, 4, 5 as long as we don't care about order.

In practice, naively using of a FFT-based algorithm to actually expand the polynomials, the multiplication of K polynomials with total degree D is O(D*log(D)*log(K)). In this specific problem, K is the number of coins and D is given by n + floor(n/a1) + floor(n/a2) + ... + floor(n/ak). If for some reason you had coins of every size, an upper bound for this could be as bad as
O(N^2*log(N)^2), but for small numbers of coins, this method could be beneficial.

A better way in practice could potentially be to use an automatic differentiation algorithm to compute the n'th derivative of the above function and the simply evaluate this at zero and divide by n!, but I do not know enough about such algorithms to actually give the time complexity reliably.

Ответить
Huy Le
Huy Le - 13.11.2023 06:20

Finally, I have been relieved of the nagging question to myself: why is it named "dynamic programming"? Which seems like an over-generalized one and virtually conveys no meaning. Surely memorization has a dynamicity characteristic, but it would be a shoot in the dark for someone to be able to infer from "dynamic" to "memoization".

Ответить
Aniket Tiratkar
Aniket Tiratkar - 09.11.2023 07:52

Great explanation and visuals! I got very high hopes for this channel.

Ответить
Sazh
Sazh - 08.11.2023 01:38

There's a slight issue for Coin Problem: How many ways
The given solution does not account for duplicates such as 1+1+2 and 1+2+1 (which together should count as 1 possible solution instead of 2)

The example 5, [1,4,5] should have an output of 3:
1+1+1+1+1
1+4
5
But instead is 4 because it counts 4+1 as a separate solution to 1+4.

An iterative solution that handles this would be for example:

memo = defaultdict(int)
memo[0] = 1
for coin in coins:
for i in range(coin, amount + 1):
memo[i] += memo[i-coin]
return memo[amount]

Ответить
Yogesh
Yogesh - 05.11.2023 11:16

Amazing, I think everyone should check it first before start learning DSA

Ответить
Emeka Ezekwem
Emeka Ezekwem - 04.11.2023 18:34

well put together

Ответить
Anon Anon
Anon Anon - 01.11.2023 13:52

Гуд найс, вэри найс. Ставлю лукас.

Ответить
M D
M D - 01.11.2023 03:51

great

Ответить
commarchinin
commarchinin - 28.10.2023 15:40

Edit: wanted to be clear that I really enjoyed the video, which I did! Initally overlooked saying that in the nature of function calls rabbit hole.

Disclaimer: if the 'naïve' recursion approach is 'naïve', it's only so because the compiler you're using is trash. Good compilers do tail call elimination!

After all, function calls having stack overhead is a high level language implementation choice, not absolute truth. For example, Forth function calls (and recursion) have no stack effects.

Fundamentally, a recursive call can always be transformed to a jump instruction rather than a call instruction. And if that doesn't happen in your toolchain, it is your compiler's fault and you should desire better.

And I know a common response to this is, 'but... then my stack trace won't show recursive calls (looking at you, Cadence SKILL).' And no, it won't. But like, the stack trace doesn't show loops either, and we're just fine with it. It's really a non-issue.

P.S.:
Extract out memoization from the functions and make it a higher order primative! Kinda hurts that you're doing it by hand.

Ответить
ollie Cook
ollie Cook - 28.10.2023 15:07

Is there a syntax highlighting like that for c? I really like it

Ответить
Denis Boksha
Denis Boksha - 27.10.2023 09:21

Thank you

Ответить
Erwan Michardière
Erwan Michardière - 26.10.2023 23:04

Hey, thanks for the great video, it's awesome, however I noticed a small error on the "How Many Ways" code, you make use of defaultdict for memo with (lambda _: 0) on line 5, which is why you needed to add memo[i] = 0 on line 9. If you declare memo as defaultdict(lambda:0) on line 5 you can supress line 9 as the lambda won't need an argument anymore to return 0 when accessing memo[i] which is not yet assigned on line 16.

Ответить
hyqhyp
hyqhyp - 25.10.2023 14:32

Part 2 please!

Ответить
Music D. Looped
Music D. Looped - 25.10.2023 07:16

great video, very precise , concise and explanatory

waiting for more, keep it up!!!

Ответить
KK T
KK T - 25.10.2023 04:21

I knew the examples but not knowing what dynamic programming is until watching this nice explanation. It is like connecting broken pieces into a large one. look forwards to next part

Ответить
Lap Wah Lee
Lap Wah Lee - 24.10.2023 20:19

Excellent presentation. Title says Part 1. Will there be more content?

Ответить
Domodiak
Domodiak - 24.10.2023 19:02

6 by 9 grid

Ответить
Guido Campuzano
Guido Campuzano - 24.10.2023 01:43

Beautiful presentation. What tool do you use to do them?

Ответить
paso
paso - 23.10.2023 10:19

The Maze problem can also be solved without DP. If you consider a move along the x axis as the letter 'a' and along the y axis as the letter 'b', a path from the upper left corner to the bottom right is a string composed by N 'a's and M 'b's. To find all the paths we just need to calculate all the permutation of the string that are (M+N)!/(M! * N!).
This approach is not generalizable but should be more efficient

Ответить
semtex
semtex - 22.10.2023 22:26

Well explained, even I got it 😂

Ответить
birthdates
birthdates - 21.10.2023 15:44

This was extremely useful and is one of the better dynamic programming explanations I've seen.

Ответить
Tim Seebode
Tim Seebode - 20.10.2023 22:59

Unbelievably well done video👍👍 you deserve many more subscribers!!

Ответить
World Class Mind
World Class Mind - 19.10.2023 16:52

Have you ever used DP to solve real world programming?

Ответить
Matt Beauvais
Matt Beauvais - 19.10.2023 08:15

The last minimum coins solution you did seems wrong. For list [2,3] and m = 4 you’d get an error trying to add None and Int

Ответить
AJ Zack
AJ Zack - 19.10.2023 03:03

nice video mate

Ответить
Nicolas Lupi
Nicolas Lupi - 18.10.2023 03:49

Gold. Can't wait for the second part

Ответить
Gheorghe Matei
Gheorghe Matei - 17.10.2023 22:20

Subject-Oriented Programming is the future. See videos.

Ответить
Igor Beaver
Igor Beaver - 14.10.2023 21:58

Very looking forward to the 2nd part!

Ответить
Mauro Lima
Mauro Lima - 14.10.2023 18:16

Hope this channel grows a lot.
I'm on mu first steps on coding, but I know it's gold.

Ответить
FrodoxDarkDragon
FrodoxDarkDragon - 14.10.2023 16:05

I cannot wait for the second part :D

Ответить
Mateusz Adamowski
Mateusz Adamowski - 11.10.2023 13:36

In this example you can even simplify the code further by using `@functools.cache` decorator.

>>> functools.cache._doc_
'Simple lightweight unbounded cache. Sometimes called "memoize".'

Ответить
megamaser
megamaser - 10.10.2023 03:23

For the Minimum Coins problem, even with memoization, you are still visiting too many nodes in the tree.

The recursive approach is a depth-first search that expands the entire tree one branch at a time. It won't find the answer until it calculates the full depth of every single branch. That means you will visit some very deep branches that you should have known you could ignore once they exceeded the minimum depth to zero.

The bottom-up approach also expands the entire tree, plus a bunch of states that may not even part of the tree, which is worse than the recursive approach. But in practice, it is faster than the recursive approach, since recursion itself is quite expensive.

A top-down breadth-first search is faster than either of your approaches. In the overwhelming majority of cases, you'll come to the solution before expanding the entire tree. Instead of memoization, you can use branch elimination to avoid expanding redundant sequences.

I implemented a top-down breadth-first search in python that in my testing ranged from 2-5 times faster as either of your implementations:

def minimum_coins(m, coins):
seen = set()
if m == 0:
return 0
layer = [m]
depth = 1
while True:
next_layer = []
for node in layer:
for coin in coins:
subproblem = node - coin
if subproblem < 0 or subproblem in seen:
continue
if subproblem == 0:
return depth
next_layer.append(subproblem)
seen.add(subproblem)
if len(next_layer) == 0:
return None
layer = next_layer
depth += 1

Ответить
F Mic Tsang
F Mic Tsang - 08.10.2023 10:57

Its really helpful. Thanks.

Ответить
Tarek
Tarek - 07.10.2023 03:03

Thank you for this awsome content. So in a nutshell by saying "dynamic programming ", that's meen benefiting from computer storage or memory capacity to solve hard problems (NP hard) that are to complex to solve in terms of times ?

Ответить
Koushik Sinha
Koushik Sinha - 06.10.2023 00:49

Loved your content, need more of these :)

Ответить
Tree Librarian
Tree Librarian - 05.10.2023 17:57

wonderful video! so well explained! I had a weird distorted view of what dynamic programming meant before this.

while thinking about the maze problem it occurred that it's really a 2D Fibonacci series.

also, only a 1d array is needed, reducing memory complexity and cache usage. you can even keep a running total for each column, initialized to 1, and forgo the initial setup (except for zeroing the array memory) halving the memory reads.

in C looks like:

int paths(int n, int m) {
int t;
if(m < n) { t = m; m = n; n = t; } // n rows is smaller dimension
int memo[--n] = {0}; // reduce n by one since first row is handled by t = 1 below
for(int i = 0; i < m; ++i) { // column counter
t = 1; // first row always 1
for(int j = 0; j < n; ++j) { // row counter
t = (memo[j] += t); // do the work
}
}
return t; // we know what the final value was already
}

/// asm version (linux calling convention)

.paths:
cmp rdi, rsi
cmovlt rax, rsi
cmovlt rsi, rdi
cmovlt rdi, rax
dec rsi
mov rcx, rsi
mov rdx, rsp ;; using stack space directly for array
xor rax, rax
.zloop
mov [rdx], rax ;; memory clearing (using int64's here)
sub rdx, 8
sub rcx, 1
jnz zloop
.iloop
mov rax, 1
mov rcx, rsi
mov rdx, rsp ;; reset running total, array address pointer and row count each column
.jloop
add rax, [rdx] ;; do the work
mov [rdx], rax
sub rdx, 8 ;; iterate
sub rcx, 1
jnz jloop ;; inner loop should execute once per clock cycle
sub rdi, 1
jnz iloop
ret ;; result is already in rax, no registers needed to be spilled to stack

Ответить
yzr
yzr - 05.10.2023 01:41

Hey, I almost never comment, but your video is really amazing. After watching it and refreshing my brain about DP, I managed to solve a new medium DP question on Leetcode without help!! (DP is one of my weaknesses lol)

I’m looking forward to watching your future video on harder DP questions!

Ответить
ArchonLicht
ArchonLicht - 04.10.2023 15:42

Very nice and clear video. Thank you!

Ответить
Nelson Nelson
Nelson Nelson - 02.10.2023 20:33

Great stuff. Do you know of any real world applications for dynamic programming?

Ответить
jmw150
jmw150 - 28.09.2023 21:19

That these are only for interview problems, shows what is wrong with society.

Ответить
Jonas K
Jonas K - 27.09.2023 10:07

There's one insight I've had about bottom-up vs. top-down dynamic programming which I've had recently.

To be concrete, let's say the top-down solution builds a memoization by a recursive function first checking whether the answer to the current call is memoized, then computing and storing it if not. The computation is done by the function recursively calling itself with smaller arguments.

On the other hand, a bottom-up solution builds the same table by calling the function with the smallest arguments first, then larger ones, in such a way that the function is never called twice with the same arguments, and when the function is called the table never has the answer already (for the arguments of that call).

I would generally expect the bottom-up solution to be faster: the overhead of checking whether the table is full has been removed, as has the redundant memoized recursive calls—they are replaced by an unconditional table lookup. The major exception is if the top-down solution can fill out the table sparsely: then it can skip the work needed to fill out unnecessary table entries, and automatically does so. [But if that's possible, can't the bottom-up approach do the same, after a bit of thinking?]

Ответить
Phenan Rithe
Phenan Rithe - 26.09.2023 19:11

No need to modify the function to implement memoization: just import functools.lru_cache and add the @lru_cache() decorator to the function (you can even remove the parentheses in 3.8 and later).

Ответить
uuuummm9
uuuummm9 - 26.09.2023 11:03

I am going to try to solve my first dynamic programming problem on leetcode after this video. Let's see how it goes! 😄

Ответить
Mikkel Madsen
Mikkel Madsen - 25.09.2023 13:27

Hey, Nikola!

This was a really useful video, as we're currently going through DP on my Master's. It's such a difficult paradigm to get used to, but your video really helped understanding the paradigm, and hopefully it'll help my future self learning the DP paradigm :)

Also, any idea when the next part is coming out? :D

Ответить
temurson
temurson - 24.09.2023 10:22

Appreciate your video! I'm decent at algorithmic problems, and knew all of the basic dynamic problems you mentioned in this video, but I liked your emphasis on first writing a brute force solution and then optimizing it.

I was a bit confused by your choice to always use bottom-up approach, because in my opinion bottom-up can sometimes be difficult to write as it can be hard to determine which states to update first. I've always found the recursive approach more intuitive, but maybe it's just me.

Looking forward to part 2! Hope you can help me find some intuition to solve harder DP problems as those are still pretty difficult for me.

Ответить
Sgene9
Sgene9 - 23.09.2023 19:21

I'm curious to know whether bottom up approach for minimum coins problem ended up calculating some intermediate values that were never used

Ответить