Coin Change Problem | Dynamic Programming | Leetcode

This video explains a very important and famous dynamic programming interview problem which is the coin change problem.It is a variation of Unbounded knapsack problem.In this problem, we are given an array of coin denominations and an amount to be formed.We are required to pickup coins of any denominations any number of times and form the given amount.We need to form the amount using minimum number of coins and return this minimum coins as our answer.If it is not possible to form the amount then simply return -1.I have explained the problem statement using simple examples and I have also shown the idea an intuition to visualize a solution for the problem.I have first explained the recursive solution idea and then I have explained the tabulation dp approach.At the end of the video, I have also shown the code using dynamic programming in both CPP and JAVA. CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
CODE LINK: gist.github.co...
USEFUL LINKS:
Coin Change 2: • Coin Change 2 | Dynami...
01 Knapsack Tabulation DP: • 01 Knapsack Tabulation...
#coinchange #dp #knapsack

[@vishalvikram8637]

People only love to listen 1 Roadmap for first year. 2 Roadmap for last year. 3 How to improve DSA. And bla bla bla.... Main thing is that.. Question se hoga gyan ki batoo se nhi. Keep dowing ur good work. My ranking has been improved much bcoz of u only

[@techdose4u]

😅

[@madhav3444]

he just roasted the excuse makers

[@buzzfeedRED]

@@techdose4u :at 9:11 , if we have NO Coin annd Amt > 0: Then we shoul return -1. Isn't it? why we return Infinity?

[@dhruvpurwar6642]

@@buzzfeedRED since we are taking min at each point , it will give result -1 even for valid points.. That's why we take INT_MAX wherever we use min

[@AYJ959]

Yeah you are right buddy

[@VikasSingh-yw3lp]

never have i seen this much to the point solution and explanation ever before!

[@Cloud-577]

I was really scared to approach dp questions but you saved me with this playlist. Thank you!

[@TejusNataraju]

Excellent explanation and kudos to the efforts! Keep going TECHDOSE :)

[@techdose4u]

Thanks

[@vishalplayzz2580]

thanks a lot man !! i only search for techdose and striver for leetcode problems keep up the good work

[@aakashgoswami2356]

Legend is back again.....

[@techdose4u]

😂

[@SurajYadav-bc5id]

too much high quality content. Loved it 3🔥🔥🔥

[@techdose4u]

Thanks :)

[@satyam2921]

Thankyou, thankyou very much 🙌, I was really struggling to solve this

[@techdose4u]

Welcome :)

[@ajaypatidar]

Thank you sir, finally i learn this method after watching this

[@himansuranjanmallick16]

Finally done😍, thanks sir for this selfless things.

[@arvindg553]

1 feedback Quality of video is Gold One thing is that main logic of program is not pressured Here include coin as many times as we want until available so 'i' remains 'i' this i can get it after so long time But beginner might not So please repeat main logic more than one time

[@techdose4u]

👍🏼

[@arvindg553]

@@techdose4u Reply from you is making joy and happy Love you TECH DOSE from Bangalore Actually my entire class is being crazy with this channel ❤️

[@techdose4u]

Great. Let's meet sometime. I am in bangalore too. I would like to meet your entire class 😜

[@anshuofficial166]

Can you make a video for a range of data types, which to use when, like I was using INT_MAX but it gave me the wrong answer, but when I use 1e5 I give me the correct answer

[@buzzfeedRED]

:at 9:11 , if we have NO Coin annd Amt > 0: Then we shoul return -1. Isn't it? why we return Infinity?

[@johnademola528]

This solution is superb. Though, I tried running it for some Test cases and it failed. E. g Test Case coins = [2] and amount =3 failed. I changed this dp[n][amount] > Math.Pow(10, 5) ? -1 : graph[n][amount] to dp[n][amount] >= Math.Pow(10, 5) ? -1 : graph[n][amount] and it worked

[@techdose4u]

Nice :)

[@johnademola528]

Thank you

[@techdose4u]

@@johnademola528 welcome :)

[@SatishKumar-nh1oq]

Thank you. I was struggling for this edge case.

[@johnademola528]

@@SatishKumar-nh1oq you are welcome

[@vairamuthu2748]

while considering coin 2 , we can expect some minimization on previously considered coin such as 1 , why are we not considering that. what is the reason ?.

[@princeanthony8525]

Why is the first row Infinity and NOT Zero. Not possible is same as Zero correct ?

[@pranayprasad50]

Nice explanation sir, But if you work on your voice modulation it will be more fun because the pitch of the voice is constant so I was feeling a bit sleepy 😅, But really it was a good video 😊.

[@intunewithishan5386]

How this testcase's expected answer is 20? Which combination of coins would make the amount 6249? [186,419,83,408]

[@virendranaik1893]

well ..did u get the answer?

[@intunewithishan5386]

@@virendranaik1893 no . Not yet

[@justanaverageguy4739]

I think it can still be optimized. We can reduce the space by using 1D array

[@techdose4u]

👍🏼

[@mohansurendar7429]

But, how bro?

[@demokraken]

so, the video is 23 minutes long. With existing pictures and code... On interview it is assumed that a candidate 1. Understands the problem 2. Comes up with the right solution (never seen it before, right?) 3. Produces correct code along with entertaining an interviewer with comments on every step as this process is not stressful enough already! How realistic is this for an hour timeframe?

[@starc701]

interleaving-strings sir, this question always freak me out , i never get how it works.

[@techdose4u]

Okay

[@abhinavkumar6344]

tooo nice way of explaination

[@prashantverma7843]

well explained as compare to others clears all my doubts

[@techdose4u]

Nice

[@ankitkumarmishra5198]

memozized code for the above problem: #include using namespace std; int coinChange(int index,int sum,vector& s,int n,vector&dp){ if(sum==0) return 1; if(index>=n||sum < 0) return 0; if(dp[index][sum]!=-1) return dp[index][sum]; if(s[index]>n>>sum; vector s; s.resize(n); for(auto &i:s) cin>>i; vector dp(n,vector(sum+1,-1)); cout

[@sirasanihemaspandana7390]

Sir is it possible to solve with out using dynamic programming Coins= list(map(int,input(). split ())) Coins.sort() Count=0 amount= int( input ()) for I in range( Len(coins)): temp = amount dividecoin = amount//coins[-i] amount= amount-coins[-i]*dividecoin if( temp ~= amount): count+=1 if( amount== 0): Print (count) break else: Print ("-1") Sir will it work ? Could you please check?

[@sirasanihemaspandana7390]

Count += dividecoin

[@gvnchandra]

wonderful explanation, thank you sir.

[@dhanashreegodase4445]

COULD NOT UNDERSTAND HOW U R FILLING TABLE FOR ACH PROBLEM

[@techdose4u]

??

[@manishthapa8860]

very nice explanation

[@RakeshKumar-yh7ro]

Great explanation thank you

[@techdose4u]

Welcome 😀

[@amitavamozumder73]

Please make a video where we can output the path we took to reach min no of coins, do we need to maintain an array for each cell? or can we just have an extra flag like inclusion or exclusion on each cell and count from that?

[@amitavamozumder73]

nevermind figured it out, we just need a boolean value in each cell, showing, included or not, then we can backtrack using the same logic.

[@0anant0]

Very nice explanation! In your code, you have initialized dp 'as we go'. What is a better way: initialize dp before the loops (special cases for row zero, col zero, etc) or as you have done here?

[@techdose4u]

Initializing before will be better because no of comparisons will decrease.

[@mdarifnufqqdugir3278]

Best explanation ❤️❤️

[@revanth6476]

cl = list(map(int, input().split())) tar = int(input()) sum=0 c=0 i=0 cl.sort(reverse=True) while sum

[@camilocuervo8271]

How can I know the coins, I mean, how many of each one according to the table

[@techdose4u]

You need to store that information separately.

[@camilocuervo8271]

@@techdose4u Do you have any idea of how?

[@sirasanihemaspandana7390]

Great Explanation Sir 👌👌

[@abhinavreddy1083]

good explanation .... thank you

[@techdose4u]

Welcome

[@xyzpqr7282]

[186,419,83,408] 6249 Doesn't work for this test case 😶 ???

[@Aks-47]

have a look at this code. int coinChange(vector& coins, int amount) { int target=amount; long int dp[coins.size()+1][target+1]; for(int i=0;i

[@xyzpqr7282]

@@Aks-47 I have written exactly the same code in java but don't know why it's not working for this test case only.

[@Aks-47]

@@xyzpqr7282 bhai if you have copied what he said, either take long int in cpp or make int max - 1, idk about java :(.. Check leetcode solutions then :)

[@shaikhnabeel6443]

me watching the colourful sentences : 👁👄👁 then watching it again because i didn't focused on explanation🥴

[@techdose4u]

😂

[@rahulbhatija1680]

Thanks, dude! It helped.

[@techdose4u]

Welcome :)

[@syedkaja2045]

what are the base cases for recursive solution

[@techdose4u]

Both recursion and DP have same base cases. I showed it.

[@dhruvpurwar6642]

@@techdose4u a base case of val

[@ayyappahemanth7134]

Content was really good but straight 25 mins is somewhat overwhelming for me! But content was great, if upossible cut down the time of each video!.. but the content was really great!

[@techdose4u]

25 mins is normal for DP 😅

[@ayyappahemanth7134]

@@techdose4u Can't say no but try!

[@vishalvikram8637]

He consider every level students. From pro to noob. So its ok.

[@AbhishekSingh-fo9nv]

watch at 1.25x or 1.50x

[@TejusNataraju]

@@AbhishekSingh-fo9nv true !!!!!

[@abhiramnatarajan8093]

Well explained!

[@techdose4u]

Thanks :)

[@ajitheshgupta3017]

Can someone please explain that j-coins[i-1]

[@sushantkumar4917]

bht confusing 😐

[@arindam1249]

best

[@pendyalaabhishek8866]

can any one tell me memoized approach.

[@mwshubham]

Thank you :)

[@syedkaja2045]

superb!!!

[@techdose4u]

Thanks

[@utkarshpanwar2358]

please upload the video of z algorithm

[@techdose4u]

Sure

[@utkarshpanwar2358]

@@techdose4u and please specify the difference b/w normal z algorirhm and improved version which having two intervals l and r how this is optimised then normal or without interval z algo thanks

[@tanveer.shaikh]

We could have sort the array and start picking and increamenting the count

[@flymaster28]

That would be a greedy approach and wouldn't work in cases like: coins=[3,4,5] with amount=11. The returned value would be -1 since you would take 2 5s and be at 10, even though you can solve it by picking 4,4,3.

[@mahipalsingh-yo4jt]

first comment !!!!!!!!!!!

[@techdose4u]

Great :)

[@267praveen]

And a totally useless one !!!

[@pragyakalyanammaitrai4933]

if no coins && amt>0 why we use infinity why we are not using 0 instead of inf @TECH DOSE

[@snehabaser3155]

Because in all prev case we use max condition. Here we wanna find min no of coins. And here if we fill 0 then min is always 0 . Hope u understand :)

[@tanayshah275]

Posting recursive solution just in case if anyone wants to take a look def min_coin_required(self, coins, m, n): if n < 0 and m > 0: return maxsize if m == 0: return 0 if coins[n] > m: return self.min_coin_required(coins, m, n - 1) return min(1 + self.min_coin_required(coins, m - coins[n], n), self.min_coin_required(coins, m, n - 1)) def coinChange(self, coins: List[int], amount: int) -> int: ans = self.min_coin_required(coins, amount, len(coins) - 1) return -1 if ans == maxsize else ans