Steps to solve any DP Problem | Dynamic Programming Bootcamp | Day 2/6 | IIT Gandhinagar

[@PriyanshAgarwal]

This is the 2nd lecture in the series. In case you just starting with DP, the first lecture would be a better place to start. kzbin.info/www/bejne/fV7Yo5x5pc-GhaM&ab_channel=PriyanshAgarwal

[@deepakantoj432]

45 : 57 how is that you're saying dp[i] is not dependent upon dp[i-8] ........ it is dependent on the past results right . dp[i-8] is a previously stored result so it shud be dependent . correct me if i'm wrong and also that if dp[i] not dependent on dp[i-8] why so that dp[i+1] also not dependent on dp[i-8]

[@al-mamunsalauddin553]

@@deepakantoj432 He was right.dp[i] is not dependent on dp[i-8].it only dependent on dp[i-6] to dp[i-1] as the transation was designed.I think you should rewatch this lecture.

[@utkarshsharma5815]

Simply amazing. If you could make similar series in increasing difficulty for topics like graphs, etc they would probably be received well too

[@dnspavankumar695]

Maturity is when you realise dp >>>graphs

[@sahilanand30]

1:47:01 how those series of WAs makes you master

[@arunachalamm3399]

Hope people will realise that this video is a gold mine for dp and priyansh ur method of solving using State,Transition base problem and final subproblem is golden. Thanks a lot!! Expecting more videos of this type

[@Manu-rm9uj]

hey in which year are you arunachalam

[@DivyamGupta-w3b]

can be get graph series ,I loved this one

[@rishabpurba3268]

the code for the first problem was simply awesome , great

[@ujjawal_]

thanks for providing content.

[@taniabanerjee4229]

SUCH A GREAT SERIES

[@aarushiagarwal8938]

Great approaches and ideas🌟🌟🌟🌟🌟🌟

[@yourbestie4138]

@1:20:50 greedy will work , i solved this question using bfs #include using namespace std; #include #include using namespace __gnu_pbds; template using ordered_set = tree; template using ordered_map = tree; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); long long n; cin>>n; queue q; q.push(n); long long lvl = 0; while(q.size()!=0){ bool flag=false; long long sz = q.size(); while(sz--){ long long x = q.front(); q.pop(); if(x==0){ flag=true; break; } string s = to_string(x); long long maxi = 0; for(int i=0;i

[@dank7044]

bhai bfs is also a way to look at all possibilities so it aint greedy

[@thusspokezarathustra4130]

I couldn't code the minimizing coins recursive approach. I tried to go back to numWays, but I did not get it to work. How to take the minimum when looping over the coins?

[@ravikjha07]

Well it depends on the constraints as such, if constraints are low. I will go with the memoization one because its easy to think. But if constraints are bit high, I will first memoize it to get the idea and then tabulate it 😅 At 50:18

[@AyushKumar-ez1xj]

Till now i am solving all dp problems iteratively and thought it i was doing it recursive😂😂😂😂 Now i have to learn how to solve it in a recursive way!

[@035asadali8]

people learn recursive because iterative is not easy to come up with ,so be happy bro

[@_PiyushKumar-vv7ui]

Great content!!! Just a small correction, We need to update current[5] = 0, inside the loop after the creation of current vector, otherwise we will get extra answers.

[@kush-cp8kc]

HEY PRIYANSH, CAN U PLZ GIVE THE LINK OF THE MINIMISING COINS RECURSIVE SOUTION , SOME ERROE IS COMING

[@amanrubey]

Ah I simply love iterative dp ♥

[@zunzarraodeore1837]

how did the following state and transition occur for the minimum coins problem . can you also give the code for the following.

[@rishabpurba3268]

i really don't get the problem 2 where the guy asked to solve the problem from a different method , priyansh said that dp[i][j] = dp[i+1][j] + dp[i][j+1], what about the when we reach n, there is no n+1 . how do you resolve this, i think it will be solved by the same method , instead of i,j is 0,0 , we will take what i,j itself. someone pls help me out here

[@deepakantoj432]

the way you explained what a state and a transition is and how you applied it in these problems ..........thanks a lot for the effort . i've scouted almost the entire internet just to understand how the dice problem works ....bcz there's this subset sum 4 on leetcode somewhat a similar one . i couldn't grasp how the intuition behind the formula works ...... errichto , utkarsh gupta , aditya verma , striver , and a great russian programmer , the mit course , karthik arora and some random blogs ...... ( not undermining their teachings but .. maybe it was too much for me to take in ) i still couldn't wrap my head around the dice problem ...finally ended up byhearting the formula felt very bad .....first time in my coding experience i byhearted a formula without having that satisfactory feel of understanding how it and why it works the way it works ..... i was even dry running the code but what's the point .......it would work i know that much but why and how ... you've given crystal clear clarity over what a state is , what a transition is ... thanks man keep up the good work .

[@Rohit_Gunwal]

In Minimizing Coins problem, Recursive dp is giving tle, only iterative dp works there.

[@abhinavgupta4778]

problem 3 is giving TLE in 4 test cases using the recursive method you suggested in the beginning. Can you clarify that if the recursive method is not suitable for this or I'm making some mistake in it?

[@PriyanshAgarwal]

Look at the first concept that I talk about in Day 6. You might be missing that concept.

[@abhinavgupta4778]

@@PriyanshAgarwal Ok, I have not reached there yet, but will check it out. Thanks for replying.

[@skandguptmaurya797]

Can you please provide some of the question links from codeforces that comes under whatever you have taught us till now in this dp series. PS: Love you content, and really learning a good way to approach dp problems. ❤

[@PriyanshAgarwal]

The slides and homework problems are in the description

[@skandguptmaurya797]

@@PriyanshAgarwal I was asking for some more problems to practice.

[@joyboy1088]

Hey, priyansh what's your sublime text theme ?

[@MOHITRANA-to7rf]

brogrammer .. thanks me later

[@Rayhan_Sefat]

Amazing lecture

[@MOHITRANA-to7rf]

I saw the first 3 and eventually solve the removing digits by my own

[@SurajGaud]

thanks for these sessions! Thankyou

[@shubham6989]

can someone share the recursive dp code of removing digits.

[@ayushwalker2003]

int help(int n, vector &dp) { if (n == 0) return 0; // debug(n); if (dp[n] != -1) return dp[n]; int ans = INF; int cn = n; while (cn > 0) { int rem = cn % 10; cn /= 10; if (n >= rem and rem != 0) ans = min(ans, 1 + help(n - rem, dp)); } return dp[n] = ans; } void solve() { int n; cin >> n; debug(n); vector dp(n + 1, -1); cout

[@MOHITRANA-to7rf]

Day 2 Abhigyan Rocks PS - if i spell it correctly !

[@fashionvella730]

coin combination 2 problem can not be solved without using space optimation

[@ppl_call_me_tima]

1:27:27 they even added one more testcase #14, which still accepts a greedy solution. funny

[@abhavgoel9390]

is it bad that i find recursive dp more intuitve?

[@PriyanshAgarwal]

Not at all. That is absolutely fine. However, you won't be able to use some optimizations like space optimization, transition optimization with recursive dp.

[@educatingbetter2179]

Love the session curated with good experience bhaiya

[@01utpalraj95]

Thanks alot

[@ekanshgupta2930]

in problem 1 hint why have we called the function dp[n] += numberofways(n-i) can someone please explain

[@kumaramit04-q6c]

if n = 3, we can make 3 like (1,1,1), (1,2), (2,1),(3). So, basically we're adding up all the possibilities that will lead to n = 3 using dice numbers from 1 to 3. Here,we can't use dice number 4, as it's not possible to make n = 3 with that. We can also add a condition inside the for loop to avoid n < 0 base case. if (n >= i) dp[i] += numberOfWays(n-i);

[@ekanshgupta2930]

Ok ok got it thanks

[@prachitiparkar8167]

It would be helpful if you had also taught the first problem if the order doesnt matter and what changes would need to be made to the code

[@PriyanshAgarwal]

Lecture 3 has that problem xD.

[@kushalavardhan]

Hello priyansh bhaiya.... delighted to learn from your lectures. please help me with a problem. in the problem "minimising coins" from the cses problemset, for input 1000000, the recursive dp is not printing anything. #include using namespace std; long long dp[1000001]; void _initialize(){ for(int i=0; i> n >> x; long long cns[n]; for(int i=0; i> cns[i]; _initialize(); for(int i=0; i

[@abhaytiwari5991]

Please take more class bro if you can.

[@PriyanshAgarwal]

I will be posting 1 lecture everyday till saturday don't worry.

[@ScaryYokai]

While submitting code in Python in cses using dp some test cases are still giving TLE rest answers are correct, is it because Python is slower or do I need to worry?

[@7_ajinkya]

python is slower. i checked all answers available and still it gives TLE. better to just learn approach to solve dp problems for now. to completely eliminate TLE problems use c/cpp

[@shiftcommand]

+1 ❣️

[@suryadharamgudi7712]

og🔥🔥🔥🔥🔥🔥

[@DigvijayGuptaofficialdk]

1st homework problem , does not passes all the test cases, with given state and transition and code. anyone can help would be appreciated. #include using namespace std; int helper(int n,vector& dp){ if(n==0){ return 1; } if(n n; vector dp(n+1,-1); cout

[@shubhamsinha2765]

Recursive solution won't work , do iterative one

[@niteshsaxena03]

first of all you should run loop from 1 to 6 and not 0 to 6 and also you need to do mod operation with 1e9+7 after every iteration

[@uptonogood300]

🔥

[@deepakantoj432]

45 : 57 how is that you're saying dp[i] is not dependent upon dp[i-8] ........ it is dependent on the past results right . dp[i-8] is a previously stored result so it shud be dependent . correct me if i'm wrong and also that if dp[i] not dependent on dp[i-8] why so that dp[i+1] also not dependent on dp[i-8] .

[@abdalaelgendy1762]

done

[@प्रेमानंद-वृंदावन]

1st

[@adityasaxena6971]

+1

[@rigvedi6000]

How to decide inner and outer loops in coin combination 2 these solutions gives different results 1) for(int i=1; i=1; j--){ int left = i-c[j]; if(left>= 0) (dp[i][j] += dp[i][j-1] + dp[left][j]) %= mod; } } cout

[@zasqqa6060]

Course is awsome but we are here to learn coding not learning concepts so at the end of every exploration and explanation you should be coding as well...... I hate your long pre written template because u should be going like