A&DS S01E10. Dynamic programming

[@chuka231d8]

The contents of this lecture: 1.Intro of DP concept with Fibonacci number sample (Naive implementation -> Memoization->Bottom Up Approach) 2.More samples of entry level DP problems - Grass Hopper problem with 2 jumps - Number of binary vectors not containing '11' - Grass Hopper problem with k jumps - Grass Hopper problem with cell costs/Path Recovery - Turtle problem in 2D grid - Again Grass Hopper problem with jump size restriction

[@DeepanshuThakuriamgsa2k14]

What a lecture and what a music at the end ❤️

[@piyushnaithani7689]

Ohh lets begin with DP❤️

[@ujjwalkumarmishra3523]

Waiting for next video on dp :)

[@saikoushik1018]

This is a one of the best lectures there for dp, thank you pavel sir

[@mr-pm9eg]

Such a great content. Love from India

[@zvenom4534]

in the last example what do we output is it dp[n][0] + d[n][1] + .... dp[n][n] ?

[@amandeep0148]

The content of the video and ending music just make my day ⭐💖. This is really really so great sir 💯💯💯💯💯💯.

[@ChandraShekhar-by3cd]

@Parvel Mavrin Thanks a lot for your effort and hard work . It is really helping us to understand the key concepts of diffrenent DS and Algo . Could you please suggest some reading resources as well for Dynamic programming. Thanks

[@anmol_tomer]

codeforces.com/blog/entry/43256

[@ChandraShekhar-by3cd]

@@anmol_tomer Thanks a lot for sharing gem.

[@amanvaibhavjha9304]

What was that resource btw, it's not there now

[@madhukiranattivilli2321]

55:00 problem : "min value path with K-jumps in O(n)" solution : "use queue implemented with 2 stacks" Hi Pavel, I tried but not confident with my approach. Writing summary below : (1) add into S2 (stack). Compute new min for every add. (2) When Q gets k+1 elements, remove 1 from S1. If S1 is empty, move all elements from S2 to S1, via pop(S2) and push(S1). (3) If min is same as removed element, move all elements from S1 to S3 (3rd Stack) via pop(S1) and push(S3), and then move all elements from S2 to S1, and finally from S3 to S1. While moving from S2 to S1 and S3 to S1, compute the new min. I think this takes amortized constant time to get min value for each cell D[i] - T = Ⲁ(1) and takes amortized linear time to finally get the min value for entire list of coins Is this correct? Or is there a better way? Thanks :)

[@pavelmavrin]

No, in your solution you may have to make (3) for every removal, so time will be O(nk). If you need to maintain min in stack with O(1) operations, you can use the following approach: make stack of pairs (element, min), when you push new element X, you push pair (X, min(top.min, X)). Basically you maintain prefix minimums for your stack

[@madhukiranattivilli2321]

@@pavelmavrin Hi Pavel, I'm very sorry. I tried really hard over 2 hours, but unfortunately I didn't understand ur suggestion. I didn't understand the use of push (X, min(top.min, X). I also didn't understand the meaning of "prefix minimums of ur stack" Please see this example (from ur lecture) : c[]: 0 3 2 6 7 1 5 4 3 0 We want to find the "least cost path using max k jumps" Let k=4. Let d[] hold the "least cost path" till that index c[]: 0 3 2 6 7 1 5 4 3 0 d[]: 0 3 2 6 7 3 7 7 6 3 So, answer is d[9] = 3 after d[4] is computed as 7, and pushed into queue, there are 5 elements, so queue front has to be pop-ed, so the sliding window get 3 2 6 7. Till now min is 0. I didn't understand how to get min=2 now in O(1) In this context, I didn't understand the significance of push(X, min(top.min, X)) If these are pushed into stack : 0, 0 3, 0 2, 0 6, 0 7, 0 after 0, 0 is pop-ed, stack should have 3, 2 2, 2 6, 2 7 2 I didn't understand how to achieve this in O(1) I'm very sorry for the super long msg.I wrote in detail so to not CONFUSE you.

[@HassanFathi2002]

@@madhukiranattivilli2321 you can just use a set , it woudn't affect much

[@arindamsarkar6522]

At 48:29 if the grasshopper jumps from 1st to 3rd box (2nd index) then the cost is 2 right? Min(2,5) is 2 right ? I am not getting.

[@arindamsarkar6522]

Oh very sorry you corrected this. :) Don't change the solution. Change the problem :)

[@tharunchowdary14]

Thanks a lot for the content, loving it!

[@madhukiranattivilli2321]

About the grasshopper problem... U took d[0]=1. It means there is 1 path into cell 0. Means the path is coming from outside. Let it be from cell -1 If so, d[1] should be 2 and not 1, because there is 1 path from cell -1 and 1 from cell 0 And d[2] = d[1] + d[0] = 2 + 1 = 3 And, for the 3-jump grasshopper... cell 2 can get a 3-level jump from cell -1. Can get a 2-level jump from cell 0. Can get a 1-level jump from cell 1. So, when we consider d[0]=1 - d[2] = 1 (jump from cell -1) + d[0] + d[1] = 1 + 1 + 2 = 4 Is this fine? Or did I misunderstand something?

[@pavelmavrin]

it depend on details of your problem, i suppose that starting point is 0

[@arindamthakur166]

56:48 can you give reference to how to calculate i-k to i-1 minimum in o(n) using stacks and queues?

[@pavelmavrin]

you can use queue with minimum, I explain it briefly in this lesson, for example codeforces.com/edu/course/2/lesson/9/2 (video "segment with small spread")

[@arindamthakur166]

@@pavelmavrin thank you.

[@madhukiranattivilli2321]

32:29 : Boolean Vectors : Hi Pavel, About the initial 2 values... U said d[0]=1 d[1]=2 shouldn't they be 2 and 3 respectively? d[0] can have 0 or 1 -- 2 vector possibilities d[1] can have 0 with 0 or 1 in d[0] d[1] can have 1 with 0 in d[0] total 3 possibilities

[@pavelmavrin]

if d[n] is the number of vectors of size n, then d[0] is number of different empty vectors, it's 1.

[@madhukiranattivilli2321]

26:56 : Hi Pavel, But aren't there 2 ways to reach cell 1? way#1: big jump to cell 1 way#2: small jump to cell 0 and another small jump from cell 0 to cell 1 So, shouldn't d[1] be 2 instead of 1?

[@pavelmavrin]

i assume we start in cell 0, so there is only one way to move to cell 1

[@achalkumar1457]

thanks sir means a lot

[@madhukiranattivilli2321]

40:00 O(n) k-jump grasshopper problem Hi Pavel, I donno what exactly u meant by Di = prefix-sum-of-(i-1) - prefix-sum-of-(i-k-1) I think I found an easier way : Di = Di-1 + Di-2 + Di-3 + … + Di-k Di = Di-1 + (Di-2 + Di-3 + … + Di-k + Di-k-1) - Di-k-1 Di = Di-1 + Di-1 - Di-k-1 So, Di = 2Di-1 - Di-(k+1) I got the same for prefix-sum approach too. Using an example. k=4 D9 = D8+D7+D6+D5 = (prefix sum of 8) - (prefix sum of 4) = (D8+D7+D6+D5+D4+D3+D2+D1+D0) - (D4+D3+D2+D1+D0) = (D8 + (D7+D6+D5+D4) + (D3+D2+D1+D0)) - (D4 + (D3+D2+D1+D0)) = (D8 + D8 + D4) - (D4 + D4) D9 = 2D8 - D4 Thus, both approaches do the same : Dx = 2Dx-1 - Dx-(k+1) Is this what you meant, or there is a more simpler way?

[@pavelmavrin]

Yes, you're right. But there is more general method. You can maintain 2 arrays: d[i] is array for your DP, and p[i] = sum(d[0..i]) is array of prefix sums. Now when you need to calculate d[i] as sum of some segment d[l..r], you can calculate it in O(1) time as (p[r] - p[l-1]). Each time you calculate new value d[i], you also calculate new value p[i]

[@madhukiranattivilli2321]

@@pavelmavrin Understood The formula I've generated - mathematical style The approach u wrote here - programming style :)

[@AlayDhagia]

where can we ask you doubts ?

[@alirezaasadi8656]

why every thing is pretty easy for him : D

[@HasanAhmed-jn8zs]

Omg is this course will lead me to lgm on codeforces ?

[@pavelmavrin]

Probably not

[@madhukiranattivilli2321]

How many cats do u hav @ home? :)

[@pavelmavrin]

none :(

[@madhukiranattivilli2321]

Hi Pavel, I noticed that you're not receiving 2nd level (and above) of my replies. Therefore, I'm writing here freshly 55:00 problem : "min value path with K-jumps in O(n)" solution : "use queue implemented with 2 stacks" Your suggestion : If you need to maintain min in stack with O(1) operations, you can use the following approach: make stack of pairs (element, min), when you push new element X, you push pair (X, min(top.min, X)). Basically you maintain prefix minimums for your stack My reply after I failed to implement : I'm very sorry. I tried really hard over 2 hours, but unfortunately I didn't understand ur suggestion. I didn't understand the use of push (X, min(top.min, X). I also didn't understand the meaning of "prefix minimums of ur stack" Please see this example (from ur lecture) : c[]: 0 3 2 6 7 1 5 4 3 0 We want to find the "least cost path using max k jumps" Let k=4. Let d[] hold the "least cost path" till that index c[]: 0 3 2 6 7 1 5 4 3 0 d[]: 0 3 2 6 7 3 7 7 6 3 So, answer is d[9] = 3 after d[4] is computed as 7, and pushed into queue, there are 5 elements, so queue front has to be pop-ed, so the sliding window get 3 2 6 7. Till now min is 0. I didn't understand how to get min=2 now in O(1) In this context, I didn't understand the significance of push(X, min(top.min, X)) If these are pushed into stack : 0, 0 3, 0 2, 0 6, 0 7, 0 after 0, 0 is pop-ed, stack should have 3, 2 2, 2 6, 2 7 2 I didn't understand how to achieve this in O(1) I'm very sorry for the super long msg.I wrote in detail so to not CONFUSE you. Could you please suggest further?

[@pavelmavrin]

1. Create stack with min() operation in O(1) time. There are multiple ways how to do it, easiest way is make the second stack of the same size, and put the current minimums in this stack. So the top element of this stack is always the minimum in the stack. 2. Create queue with min() operation in O(1) time, using two stacks. Here minimum in queue is minimum of two minimums 3. Use the sliding window technique with designed queue to solve the problem

[@madhukiranattivilli2321]

@@pavelmavrin Thanks Pavel. I found your "segment with small spread" codeforces lecture, and perfectly understood the solution. I appreciate ur consistency in answering my questions and doubts :) So, the "super point" of this idea is that... If stack S2 implements Q.add() and S1 Q.remove()… (1) When we've to pop, and S1 is empty, and we shift all elements from S2 to S1, recreate the "minimums S1" stack as we push elements into S1 (2) For any new push into S2, the corresponding "minimums S2" stack should get min(new-element, min-S1.top, min-S2.top) Perfectly understood the technique now. Thanks :)

[@pritishpal8733]

Can anyone plz share the codes for the home task given .. plzzz

[@MehbubulHasanAlQuvi]

Can we please have some lectures on Greedy Algorithms? :')

[@pavelmavrin]

I tried several times, but it's hard to make full 90-minute lecture about greedy algorithms. Maybe it's time to try again.

[@MehbubulHasanAlQuvi]

Thanks a lot, Pavel! On a different note, have you started your A&DS (English) Season 03 streams on Twitch? Any possible date?

[@amanbadone9462]

34:11 the grasshoper went to gym his muscles are strong now and he can jump k cells at a time 🤣