Coin Change Problem | Dynamic Programming | Leetcode
HTML-код
- Опубликовано: 4 ноя 2020
- 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/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL LINKS:
Coin Change 2: • Coin Change 2 | Dynami...
01 Knapsack Tabulation DP: • 01 Knapsack Tabulation...
#coinchange #dp #knapsack
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
😅
he just roasted the excuse makers
@@techdose4u :at 9:11 , if we have NO Coin annd Amt > 0: Then we shoul return -1. Isn't it? why we return Infinity?
@@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
Yeah you are right buddy
never have i seen this much to the point solution and explanation ever before!
I was really scared to approach dp questions but you saved me with this playlist. Thank you!
Legend is back again.....
😂
Excellent explanation and kudos to the efforts! Keep going TECHDOSE :)
Thanks
thanks a lot man !! i only search for techdose and striver for leetcode problems keep up the good work
Finally done😍, thanks sir for this selfless things.
wonderful explanation, thank you sir.
Thank you sir, finally i learn this method after watching this
Great Explanation Sir 👌👌
too much high quality content. Loved it 3🔥🔥🔥
Thanks :)
Thankyou, thankyou very much 🙌,
I was really struggling to solve this
Welcome :)
Thanks, dude!
It helped.
Welcome :)
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
Nice :)
Thank you
@@johnademola528 welcome :)
Thank you. I was struggling for this edge case.
@@SatishKumar-nh1oq you are welcome
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
Reply from you is making joy and happy
Love you TECH DOSE from Bangalore
Actually my entire class is being crazy with this channel ❤️
Great. Let's meet sometime. I am in bangalore too. I would like to meet your entire class 😜
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 ?.
Best explanation ❤️❤️
well explained as compare to others clears all my doubts
Nice
interleaving-strings sir, this question always freak me out , i never get how it works.
Okay
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 😊.
good explanation .... thank you
Welcome
Great explanation thank you
Welcome 😀
very nice explanation
Well explained!
Thanks :)
me watching the colourful sentences
: 👁👄👁
then watching it again because i didn't focused on explanation🥴
😂
:at 9:11 , if we have NO Coin annd Amt > 0: Then we shoul return -1. Isn't it? why we return Infinity?
I think it can still be optimized. We can reduce the space by using 1D array
👍🏼
But, how bro?
tooo nice way of explaination
Thank you :)
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?
Initializing before will be better because no of comparisons will decrease.
superb!!!
Thanks
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
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
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?
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.
How this testcase's expected answer is 20? Which combination of coins would make the amount 6249?
[186,419,83,408]
well ..did u get the answer?
@@virendranaik1893 no . Not yet
best
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?
COULD NOT UNDERSTAND HOW U R FILLING TABLE FOR ACH PROBLEM
??
Why is the first row Infinity and NOT Zero. Not possible is same as Zero correct ?
please upload the video of z algorithm
Sure
@@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
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!
25 mins is normal for DP 😅
@@techdose4u Can't say no but try!
He consider every level students.
From pro to noob.
So its ok.
watch at 1.25x or 1.50x
@@AbhishekSingh-fo9nv true !!!!!
How can I know the coins, I mean, how many of each one according to the table
You need to store that information separately.
@@techdose4u Do you have any idea of how?
cl = list(map(int, input().split()))
tar = int(input())
sum=0
c=0
i=0
cl.sort(reverse=True)
while sum
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?
Count += dividecoin
what are the base cases for recursive solution
Both recursion and DP have same base cases. I showed it.
@@techdose4u a base case of val
We could have sort the array and start picking and increamenting the count
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.
first comment !!!!!!!!!!!
Great :)
And a totally useless one !!!
[186,419,83,408]
6249
Doesn't work for this test case 😶 ???
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
@@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.
@@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 :)
bht confusing 😐
can any one tell me memoized approach.
Can someone please explain that j-coins[i-1]
if no coins && amt>0 why we use infinity why we are not using 0 instead of inf @TECH DOSE
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 :)
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