Coin Change Problem | Dynamic Programming | Leetcode #322 | Unbounded Knapsack

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:

=======================================================================

USEFUL LINKS:

#coinchange #dp #knapsack

[vishalvikram]

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

[VikasSingh-ywlp]

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

[Cloud-]

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

[ankitkumarmishra]

memozized code for the above problem:

#include<bits/stdc++.h>
using namespace std;

int coinChange(int index, int sum, vector<int>& s, int n, vector<vector<int>>&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]<=sum){
dp[index][sum] = 1+coinChange(index+1, sum-s[index], s, n, dp);
return dp[index][sum];

}
else{
dp[index][sum] = min(1+coinChange(index+1, sum-s[index], s, n, dp), coinChange(index+1, sum, s, n, dp));
return dp[index][sum];
}

}
int main(){
int n, sum;
cin>>n>>sum;


vector<int> s;
s.resize(n);
for(auto &i:s) cin>>i;
vector<vector<int>> dp(n, vector<int>(sum+1, -1));

cout<<coinChange(0, sum, s, n, dp);

}

[arvindg]

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

[VsEdits]

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

[akshadgupta]

very good solution !!! excellent knowledge

[TejusNataraju]

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

[buzzfeedRED]

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

[johnademola]

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

[revanth]

cl = list(map(int, input().split()))
tar = int(input())
sum=0
c=0
i=0
cl.sort(reverse=True)
while sum<tar and i<len(cl):
sum = sum+cl[i]
if sum>tar:
sum = sum-cl[i]
i+=1
else:
c+=1
print(c)

it works for some cases..!! and simple

[ajaypatidar]

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

[himansuranjanmallick]

Finally done😍, thanks sir for this selfless things.

[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?

[princeanthony]

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

[satyam]

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

[starc]

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

[vairamuthu]

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 ?.

[justanaverageguy]

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

[SurajYadav-bcid]

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