Coin Change 1 & 2 : Leetcode DP Questions | CP Course | EP 93

[@anonymous13679]

Thank you Luv, Can you also make a tutorial for Graph and Flows?

[@ChandraShekhar-by3cd]

Thanks a lot for the Leetocde video . Please continue with the Leetcode Daily challenge series. Thanks💛

[@anshulkumar7871]

Please complete whole DSA series before November. I understand everything you teach.

[@PoojaSharma-nt3ge]

The important difference nobody tells you! 🙌🏻🙌🏻🙌🏻 very well explained

[@codesouls2441]

Love you man. Only because of you I am able to understand dynamic programming and finally solve some problems with it. You are amazing. Thanks for this playlist.

[@Naturalbanarasi]

Very intuitive approach to problems bhaiya.

[@shubhsiroliya1213]

coin change 2 can be made in a separate video & code must have to be explained from scratch because two approaches are quite different from each other & it is hard (very time consuming) to successively watch both the videos & interpret both the algos . You're doing an amazing work keep it up , just letting you know what difficulty I faced . otherwise content is rich in quality . Thanks .

[@jonayedmohiuddin538]

class Solution { public: int dp[310][5010]; int func(int amount, vector &coins, int curr) { if(amount == 0) return 1; if(dp[curr][amount] != -1) return dp[curr][amount]; int ways = 0; for(int i = curr; i < coins.size(); i++) { if(amount - coins[i] >= 0) { ways += func(amount-coins[i], coins, i); } } return dp[curr][amount] = ways; } int change(int amount, vector& coins) { memset(dp, -1, sizeof(dp)); sort(coins.begin(), coins.end()); return func(amount, coins, 0); } }; I tried it this way by changing the code for coins change 1.

[@kuldeep-ju7iy]

exactlyy.. why he is not replying anyones comments here he made promises of : /

[@sahilanand30]

Clear and concise explanation

[@harishsharma2892]

in minimum coins if we use a test case in which no combination is possible we are not getting -1 as ans from this code if we use case like ampunt=7,n=3,coins={3,6,3} I m getting 1 as ans as it will go inside the loop .

[@gilbertopsantosjr]

what's the whiteboard are u using ? can u share the link ?

[@AmanKumarSinhaOfficial]

Please Make Videos on CodeForces Questions

[@fitness11257]

trie ke upar bhi banao videoes

[@lokeshmehta9591]

ultimate effort

[@nopecharon]

you are too good in teaching

[@ritodhwajsen8205]

Great explanation. Lovet it

[@abhijeetsingh9796]

Sir, minimum coins required ko greedily nhi kar sakte kya?

[@jonayedmohiuddin538]

class Solution { public: int dp[310][5010]; int func(int amount, vector &coins, int curr) { if(amount == 0) return 1; if(dp[curr][amount] != -1) return dp[curr][amount]; int ways = 0; for(int i = curr; i < coins.size(); i++) { if(amount - coins[i] >= 0) { ways += func(amount-coins[i], coins, i); } } return dp[curr][amount] = ways; } int change(int amount, vector& coins) { memset(dp, -1, sizeof(dp)); sort(coins.begin(), coins.end()); return func(amount, coins, 0); } }; I tried it this way by changing the code for coins change 1.

[@mehoneybadger999]

sr, ek baat bata do bs, for dp, agar mujhe iterative approach nahi aata, ya mai iterative approach me weak hu, to companies interviews or selection process pr kya affect hoga?

[@ChirameTanishqArvind]

music name ?! at the end and start of the video ?

[@kuldeep-ju7iy]

how can you ensure in the questio which was asking for minimum coins that the coins which we got our answer are making the amount zero..

[@musicascade4408]

absolute stunner exlpanation!

[@viki2479]

💛.bhiya if thecondition , if(dp[index][amount] != -1) return dp[index][amount]; is placed before other if conditions , then the program is not working.could you explain why?

[@mkitrixxmusic4023]

because index can go to negetive and accesing negetive indexed memory is not allowed :)

[@pawankumarpandit1822]

what a amazing explanation bhaiya

[@anshulagarwal6682]

If we are type casting in func(amount - coin)+1LL then it will cross INT_MAX and condition ans == INT_MAX?-1: ans should not return -1.

[@raunakkumar6144]

Think carefully , when will above function return int max. It will return int max only when making v with given coins is not possible(like making odd V with all even coins etc) so min from ans which is int max and int max +1 is int max

[@varunsharma2876]

Very well explained !!🙂

[@abhinavpandey3356]

Min coins wale ki complexity kitni hogi o(Len of aray*height of recur tree) is it correct? Height of tree can be upto the max element of array

[@_inspireverse___]

I'm little confused In knapsack problems either we take current element or skip . So we have to call 2 times recursive function. dontTake = func(amount , coins); take = 1 + func(amount - coin, coins); But you took only second case . Why???

[@shahbazp1]

'don't take' scenario will be covered automatically since there is a loop iterating through each coin denomination.

[@codecorn8030]

This happens when u see striver and Luv together 😂😂

[@divyampatro8586]

Great video Luv, I was wondering about the time complexity for Coin Change 2, it should be O(N*M*M) where N = coins.size() and M = amount. #Recursive calls = O(N*M), and computations per call = O(M). Am i right?

[@iamluv]

Salute inside every recursion is not a linear Loop only for coin of Rs.1 it will be linear even for coin of Rs.2 it will become a login loop and soon it will go on decreasing hence approximately it is near to NM only

[@divyampatro8586]

@@iamluv Agreed! Thanks for replying dude :)

[@strugglingprogrammer1487]

Love you Luv bro, for such as wonderful video of DP

[@saikatthegreat5925]

Why do you prefer memoization over tabulation? I just submitted this question on leetcide seeing your video, I submitted using memoization, it said I beat 6% of the cpp submissions in runtime. Then I gave the code to chatgpt and said to reduce runtime. He used tabulation and it beats 97% of cpp submissions. I said don't use tabulation, try reducing with memoization. He tried but the code gave wrong answer that means to me that the code cannot be optimized more.

[@PoojaSharma-nt3ge]

The selection of the similar problems to explain the difference is very well thought!

[@codecorn8030]

Bhaiya pls tell ....why the below code for the same problem with ur approach only Is giving TLE ? ------------------------------------------------------------------ static const int N = 1e5+10; int MinC[N]; int MinCoins (int sum , vector&a) { if (sum < 0) return -1; if(sum==0) return (MinC[sum]=0); if (MinC[sum] != -1) return MinC[sum]; int ans = INT_MAX; for (int i = 0; i < a.size(); ++i) { int prev = -1; if(sum-a[i]>=0) prev = MinCoins(sum - a[i], a); if (prev != -1) { ans = min(ans, 1 + prev); } } if (ans != INT_MAX) MinC[sum] = ans; return MinC[sum]; } int coinChange(vector& coins, int amount) { memset(MinC,-1 , sizeof(MinC)); return ( MinCoins(amount , coins) ) ; }

[@mumbailover-sp7tk]

bhaiya where i am getting wrong while applying second approach to first coin change problem of finding minimum count of coins required bhaiya please reply fast #include using namespace std; const int N=1e5+10; const int M=301; int dp[M][N]; int func(int index,int amount,vector &coins){ if(amount==0){ return 0; } if(indexn>>amount; memset(dp,-1,sizeof(dp)); vector coins(n); for(int i=0;i>coins[i]; } int ans=func(coins.size()-1,amount,coins); if(ans==INT_MAX){ cout

[@lordvoldemort17727]

can someone explain the coinchange2 algo. i didnt understand it completely

[@ankita7119]

same

[@SilentKiller-tp9pu]

[@anshulagarwal6682]

I was unable to submit Coin Change 2 through this solution because Memory Limit was exceeded. How can we optimize memory?

[@pulkitdang]

Can the coin1 code be modified to get the list of coins constituting the minimum number of coins required to create that particular amount?

[@leninsingh5264]

Can someone explain the iteration for(int coin: coins), How the values are stored on ans and iterating.?

[@rishav144]

thanks 🔥

[@shivamcoli3073]

sir ek video minimum difficulty of job schedule pe banao

[@SyedAli-gu2hp]

16:43 it's can be a meme "Kyu hora hai mera sath aisa"

[@avanshikasingh2054]

I really like your video. Great work 👌 Please when ever you write new fun() write it from starting . Just not edit it I just get confused some time.

[@ameykhurdekar4980]

very helpfull thankyou very much

[@abhishek04204]

Is this question comes under unbounded knapsack ??

[@romanrai2507]

Best as always❤

[@RISHAVKUMAR-kx5up]

Sir z function ki ek video bana do please

[@kishan2]

Can any tell me, why am i getting TLE with this code of coin change 1 problem: int dp[13][10001]; int func(int idx, int amount, vector coins) { if (amount == 0) return 0; if (idx < 0) return INT_MAX; if (dp[idx][amount] != -1) return dp[idx][amount]; int ans = INT_MAX; for (int n = 0; n * coins[idx]

[@yashvardhansinghsolanki659]

pass vector by reference in func

[@CodeDaily29]

can anybody explain about INT_MAX?

[@Kaushikraj9845]

But why did you select graph tree..why not regular formula of division and mod

[@pkyadav6230]

Bhai music kaon sa hai

[@chiraggoyal9646]

Thanx bhaiya

[@Ash-fo4qs]

same code not working in leetcode? anyone

[@mkitrixxmusic4023]

leet code gigving me tle for the same code in coin change 2 :)

[@funenjoynilaypatel4553]

16-aug 2022

[@AKumar11111]

Koi ye batao ki ans INT_MAX ke equal kase ho raha hai

[@unknown_coder7960]

Bhaiya ab 870 questions aur 🙂

[@kripanshbhalla9782]

cses aur vscode par nhi chal rha, leetcode par chal raha, hows that possible!! dimag kharab hogya h..

[@jasmeenkaur6001]

coin change 1 mien 2nd que vali approach work ni kr rhi bhaiya int dp[13][10010]; int Func(int index, vector& coins,int amount){ if(amount==0) return 1; if(index

[@chrisharris1892]

isliye nahi work kar rahi yah approach kyunki minimum number of coins find karne ke liye index-1 kar rahi ho par wo galat hai. Index ki koi zarurat nahi hai kyunki sequence order matter nahi karta yaha.

[@princhipawansaikia]

💛💛💛

[@hemantsingh2331]

💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛

[@subhasishpanda5390]

💛

[@sureshasuresha3571]

👌👌

[@p38_amankuldeep75]

💛💛💛💛💛💛

[@dhruvyadav3492]

💚

[@soumavachakraborty9858]

💛💛💛💛💛

[@DailysharmaKivines]

✨

[@Good-tz8ep]

❤️💕💕❤️

[@lakshyakhushalani9464]

bhaiya atleast pehle samjhao toh sahi hum begineers ko ki ques ko dekhkar kese samjhee ki yeh dp se hi hoga ya recursion se hi hogaaaaa......pehle general way toh samjhaoo

[@harshitagrawal8859]

Plz don't call it basic sa code , its difficult for newbi to grasp

[@namansharma5128]

Code Using Knapsack Concpt--> class Solution { int dp[301][5001]; //finds the ways for getting amount using all the combos of coin at the current index. int find(int ind, int amt, vector& coins){ if(amt==0) return 1; if(ind < 0 || amt the above code will also consider the duplicates combination.

[@ayushraj-lt4oc]

😂😂

[@nishchayshroff7334]

💚💚

[@tanvir4587]

🧡

[@dipubiswas8359]

💛💛💛💛

[@sayondeep5050]

💛

[@chillkro25]

🧡🧡

[@good114]

💕♥️

[@parivartan_._07]

💛💛💛

[@champion5946]

💛

[@SohamJobanputra]

💛💛💛💛

[@_ayush_oswal]

💛💛💛

[@pulkitmittal584]

💛

[@jinniesrego]

💛

[@divyanshgupta5686]

💛

[@virenderkumar951]

💛

[@divyansh2212]

💛💛

[@shivi3157]

💛

[@sahilanand30]

💛

[@aptitudepointiit-bhu5358]

💛

[@sanketkhonde4315]

💛

[@harshitsamdhani2426]

💛

[@newmoviesarena780]

💛

[@than0s869]

💛

[@ayushmansingh3700]

💛

[@rakesh1147]

💛

[@sanjaymajumder2991]

💛

[@JIGARSINGTHAKOR-yy6qp]

💛

[@NARUTOUZUMAKI-bk4nx]

💛💛

[@harshitsrivastav7343]

💛

[@Red___Beast]

💛💛