You are the only person who can explain things in the best way than others. No one teaches like that. You're a gem brother, because of you I have started loving DP
@@abdulnafe6442 make dp of size n+1 and length +1. make elements of zero length of dp to be zero. And make element of zero size of dp to be zero. dp[n+1][L+1]; in two loops { if (j==0||i==0 then make dp[i][j]=0;}
@@abdulnafe6442 You need to see the recursive logic to identify that when you don't have any item (n in recursion is same as i in tabulation ), then 0th row takes value of 0. similarly if the capacity is zero ( w in recursion is same as j in tabulation) then 0th column will take value of 0. Do watch the knapsack videos(recursion, top down) to understand the logic here in unbounded knapsack.
Sir you are great! I use to figure out such similarities in questions , but used to think they were useless. Super confident after watching your content.
Great explanation Aditya. Only 1 feedback, it'd be even better if you can do a complete dry run of 1 testcase atleast. It'll help us visualie the scenario. Drawing parallels is fine but not so easy. Like in this video, it is not clear that why your formula works!
bow down to aditya verma .. the way he teaches is just out of universe . no one teaches so good brother . Thank you so much for making my dp stronger than ever before.
A big thankyou for this DP playlist Aditya sir. You made the life easy:) Jut one thing to add for this question: When i=0 and j !=0 i.e. we don't have rod of any length to be picked up(i=0), but there is still some length remaining(j !=0), in that case the path is not feasible. Therefore, we should initialize it with Integer.MIN_VALUE instead of 0. Here is the code in java: int dp[][] = new int[n+1][n+1]; for(int i=0; i
Within 7 minutes I was able to stop the video and make a successful submission. Enjoying the binge watch and solving. Pausing and thanking you for it. Aur kaafi bacha hai.
Awesome just a small change i.e. t[i] instead of t[i-1] did the whole magic Thank you for relating the things. which makes it easy to remember and understand things
Oooooohhh bhai.......Angaar lagaa rahe ho tusi! Bus ek chotah se request, 0/1 aur unbounded ke jitne bhi problems hai unke links apne description pe daldena, practice karne ko easy hojata, Buss us question ka nahi, koi aur hatke vaale
The explaination did not clear how to identify an unbounded knapsack, only thing i could get is that in an unbounded knapsack, the elements can be repeated. please elaborate how would we know to solve a problem with unbounded knapsack as a base? Will it be mentioned in the question that repetition is allowed?
Yes, I was also thinking how to identify whether a knapsack has to be solved as 0-1 or unbounded, and Aditya didn’t gave any hint about this. According to me, in this question it is mandatory that the length of all the segments has to be equal to the length of the rod (that is N). if we’ll try solving this using 0-1 knapsack, we might not be able to get this condition fulfilled, that is in case of 0-1, there’s a possibility that the length of all the segments maybe or may not be equal to the length of the rod, because in case of 0-1 it can also come out to be less than the length of the rod, which we have seen in 0-1 knapsack problems, that the knapsack is not fully filled sometimes. In this problem the length of the rod must be equal to the sum of length of all the segments, or you can say that it is a kind of knapsack problem with an extra condition that the knapsack has to be filled completely upto its capacity. By using an element many times we might be able to completely fill the capacity, which is sometimes not possible with 0-1. So try using unbounded in cases where you have to completely fill or where you have to reach the capacity or length or anything given in the problem. And it is not mentioned in the question, if you'll check on various platforms, its not mentioned there about repetition and all.
I think the code is wrong. In knapsack the total weight of selected items need not be equal to Knapsack capacity. But in this case the total length of selected segments must be equal to Length of the rod not less.
@@TheAdityaVerma let's say state is (n, length). Say we are finding (1,9). First element length is also 9 then (1,9) = 1+ (0,0) = 1 and it's correct. But if length is is 7. (1,9) = 1 + (0,2) and since we have initialised both 1st row & 1st col as 0, (1,9) = 1 but that's wrong since we only have 7 in our array and can't make 9 length
public class rodCutting { public static void main(String[] args) { // Define the profits and lengths for each possible rod piece. int price[] = { 1, 5, 8, 9, 10, 17, 17, 20 }; // Profits associated with rod pieces. int length[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; // Lengths of corresponding rod pieces. int n = 8; // Total length of the rod. // Create a 2D array 'dp' for dynamic programming. int[][] dp = new int[price.length + 1][n + 1]; // Initialize the first row (no rod pieces) and first column (no length) of 'dp' // to 0. for (int i = 0; i < price.length + 1; i++) { for (int j = 0; j < n + 1; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; } } } // Fill in the 'dp' array to compute the maximum profit using dynamic // programming. for (int i = 1; i < price.length + 1; i++) { for (int j = 1; j < n + 1; j++) { if (length[i - 1]
Your videos are great. But here i guess it would be better if you emphasized more on approaching the problem from the rod cutting part instead of directly trying to build the code by making the values analogous to the previous question. I.e some more insight into the real problem would be great. By the way great work 👍
Very Good Aditya.. really impressed with your hard work .. I know it takes lot of time to make this .. and help everyone .. Really DP looks very easy now.
0-1/Fractional/Unbounded knapsack could be filled without reaching the capacity, but in rod cutting you need to reach the capacity (total length). How do you tackle this? @aditya
When you make a cut, u choose the price for that len. The remaining part of the rod is also optimally cut. You sum up these prices -- cur max price = curr len price + 'max' price for remaining len
Engrave this in stones and history will witness that best ever tutorials created for Dynamic Programming on entire planet was created by Aditya Verma. Period.
In given problem link many are assigning t[0][i]=INT_MIN Isn't we are talking about length here, how can we take loss?? I didn't get this, ig minimum value can be '0' only, right? then why INT_MIN?
I first thought of a 0/1 knapsack kinda approach where each "n" is --> do you want to cut here or not? if cut here, store the value, and pass to recursive call (n-1, 0) if not cut here, increment the value, and pass to recursive call(n-1, value + arr[n-1]) for each n, return max of these 2 values but that was the wrong approach. though I conceptually didn't get why it was the wrong way...
Given the stock bars of length L=12m (plenty in stock), Lengths to cut = Array(3.5, 4.2, 6.5, 5.7)m, Quantity required = Array(50, 30, 70, 45) nos. To find the minimum number of stock bars required. How to do this? Please advice.
What does a cell here represent in the table? This one seems confusing. Each column represents length of rope and each row represents what?? Can anyone explain exactly what is the cell at location i,j represents and what is i and what is j there precisely??
Each row represents the length of rod and column represents the size of array . So if we are at dp[i][j], it means that this cell gives solution when the length of rod is j and size of array is i. For example if array={5,5,2} and length = 7 then the cell dp[3][2] represents a situation in which length of rod is 3 and size of array is 2 i.e elements of array available for this length are {5,5}
Sir, on the link that you have mentioned, they have provided all the solutions using O(n) extra space but we are using O(size*N). How can we optimize it to O(N)?
yes , it is mentioned that we have to use O(N) auxiliary space, but gfg has accepted my solution even though i've used a matrix. How is this happening?
how Time can be Linear ??? May be you have mistaken with space because GFG uses 1D array(No need to keep track of items that was inserted or not). and he is using 2D array(Keeping track of items which is redundant). All Unbounded Knapsack problems can be solved by using 1D array. He is maintaining the similarity for viewers so he is not confusing people by trying to give the most optimal approach where solution may differ from one another.
In initializing the matrix when size of length array is zero ,then why we are not getting profit equal to total length. And we are initializing first column and row with 0.
Great as always Aditya :) But the code in this video is missing a case that sum of lengths of selected segments of rod must be equal to the total length of the rod. This case can be handled by changing the initialization of dp matrix as mentioned below. for(int i=0; i
Hi @Aditya Verma and everyone, I have a small confusion and need some help : There is this question in which array of pieces(size) to be cut from a rod(or ribbon or line segment) is given. and maximum length of rod(or ribbon or line segment) is given. We have to find the maximum number of segments we can make by cutting only of the sizes given. For example : max size of rod = 7 pieces allowed to cut = [5, 2, 2] (n = 3 , i.e. size of this array is 3) Correct Output = 2 (i.e. we can get "two" segments i.e. 5 and 2) I tried solving it using the approach taught above, i get 3 as my answer and I know somewhere I am going wrong. In case you guys want to see my approach, this is a small segment which explains all : (initialization has been done) for(int i = 1; i
def fun(a,n): dp=[[0 for i in range(n+1)] for j in range(4)] for i in range(1,4): for j in range(1,n+1): if j>=a[i-1]: if dp[i][j-a[i-1]]!=0 or j==a[i-1]: dp[i][j]=max(dp[i-1][j],1+dp[i][j-a[i-1]]) else: dp[i][j]=dp[i-1][j] else: dp[i][j]=dp[i-1][j] return dp[-1][-1] refer this ....,your code is correct but you only have to add one condition (my 6th line).....kyunki agar apan rod ko divide kar rahe hai toh uske saare parts (elements) given array(pieces) mai se hi hone chahiye
@@jimenluhar7126 Thanks a lot brother. Just one thing, I can understand "j == a[i-1]" which means that "piece ka size" should be in the array. But iska matlab kya hua "dp[i][j-a[i-1]]!=0" ?? Can you please explain this ? I will be very thankful
@@codestorywithMIK agr j-a[i-1] not equal to 0 hua... matlab ki apn currently jis piece k liye loop chala rahe h uske bina bhi apni rod valid h (mtlb agar puri rod mai se apan ne a[i-1] element nikal diya toh jo rod bachi hai uski length prices array mai honi chahiye ya fir usko further break kiya ja sakta h !!)
@@codestorywithMIK for example n=7 Pieces=2,2,5 Toh tumhare code k hisaab se 3 cut hone chaiye jisse 3 elements ki length 2 hogi aur aik ki 1 (2+2+2+1=7) but jo rod ka element h uski length 1 nahi ho sakti kyunki woh pieces array mai nahi h !! mtlb correct answer 2 cut h (2+5) jo valid hai
@@codestorywithMIK agar dp[i-1][j-a[i-1]] equal to 0 hua matlab ki j-a[i-1]. ko apan valid nahi bol sakte kyunki woh pieces array mai bhi nahi hoga aur usko pieces array k elements use karke bhi break nahi kiya ja sakta (use element ko apan ne pehle hi process kar liye h ).
@Aditya Verma What are the sources from where we can have hands-on on this topic.Your videos are worth watching but having a hands-on would surely clear all the doubts i guess!
atcoder.jp/contests/dp/tasks this is a complete list of DP problems, here you can practice more. (I think after watching Aditya's videos you can do all of them ).
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
Kids -> Standard Problem
Legends -> Praaacheen Problem 😂
Amazing work dude.
😂
😒😒😒
😂😂
😂😂😂
😁
You are the only person who can explain things in the best way than others. No one teaches like that. You're a gem brother, because of you I have started loving DP
tabulation method me initialization kaise karein?
please anyone explain the logic!
Thanks.
@@abdulnafe6442 make dp of size n+1 and length +1. make elements of zero length of dp to be zero. And make element of zero size of dp to be zero.
dp[n+1][L+1]; in two loops { if (j==0||i==0 then make dp[i][j]=0;}
14 of 50 (28%) done! Very nice explanation! Repetition makes is easier to consolidate with each iteration :-)
who?
What?
Why?
When?
Where?
The way you have explained dp is remarkable and highly appreciable, please start teaching other topics as well.
tabulation method me initialization kaise karein?
please anyone explain the logic!
Thanks.
The best tutorial for dynamic programming on internet.
Thank you sir for clearing the basics so well
tabulation method me initialization kaise karein?
please anyone explain the logic!
Thanks.
@@abdulnafe6442 You need to see the recursive logic to identify that when you don't have any item (n in recursion is same as i in tabulation ), then 0th row takes value of 0. similarly if the capacity is zero ( w in recursion is same as j in tabulation) then 0th column will take value of 0. Do watch the knapsack videos(recursion, top down) to understand the logic here in unbounded knapsack.
This question was asked to me this year in TCS exam. I was unable to solve it 😅. Now I can solve it easily. Thank You for awesome teaching.
digital or technical round?
@@sougatoghosh8467 technical round
@@sougatoghosh8467 bhai itna to tum bhi soch skte ho , digital round mein DP ka questions to nhi puchhta bro
reallly?
tcs asks DP?
@@Shourya_performs The TCS exam was for 9 lakh ctc, not 3.5 lakhs bro.
UNBOUNDED KNAPSACK == ROD CUTTING PROBLEM. GANGADHAR HI SHAKTIMAN H ..
😂😂😂
I haven't finished all videos but already a fan sir! 😇Thank you for teaching these topics .Keep making CP less scary, you are such a saviour 🙌🏻
You're the one who reminds me of the student who teaches us one night before the exam.
Thanks a lot for the videos.
You're truly amazing.
tabulation method me initialization kaise karein?
please explain the logic!
Thanks.
Aditya bhai!!! Do din se lagataar aapke videos dekh raha hoon!!! aaj se pehle coding seekhne mein itna maza nahi aaya kabhi!! Thanks to you man!!
Why are you not making videos nowadays?..... It's a humble request that if you have time please make a playlist on backtracking
Start watching striver's videos
@@parthsalat He is not as good as this guy.
@@humbleguy9891 I agree, but there's no other option
bro,he is roughy making 16 lakhs from his patreon alone each month,I don't think he is coming back to youtube anytime soon
Sir you are great! I use to figure out such similarities in questions , but used to think they were useless. Super confident after watching your content.
Have you yet placed or not?
Love how you repeat the explanations. Thank you for doing this for free
tabulation method me initialization kaise karein?
please anyone explain the logic!
Thanks.
pls make a playlist on graph too, maybe that will be less scary then, as dp is now
hmm
Yes plz make a playlist on graph
Thank you for existing.
Great explanation Aditya. Only 1 feedback, it'd be even better if you can do a complete dry run of 1 testcase atleast. It'll help us visualie the scenario. Drawing parallels is fine but not so easy. Like in this video, it is not clear that why your formula works!
bow down to aditya verma .. the way he teaches is just out of universe . no one teaches so good brother . Thank you so much for making my dp stronger than ever before.
tabulation method me initialization kaise karein?
please anyone explain the logic!
Thanks.
A big thankyou for this DP playlist Aditya sir. You made the life easy:)
Jut one thing to add for this question:
When i=0 and j !=0 i.e. we don't have rod of any length to be picked up(i=0), but there is still some length remaining(j !=0), in that case the path is not feasible. Therefore, we should initialize it with Integer.MIN_VALUE instead of 0.
Here is the code in java:
int dp[][] = new int[n+1][n+1];
for(int i=0; i
Within 7 minutes I was able to stop the video and make a successful submission. Enjoying the binge watch and solving. Pausing and thanking you for it. Aur kaafi bacha hai.
DP was so scary to me until your videos came to rescue!
still people watching your videos on you tube big bro....you are the real master of dsa...your way of teaching is masterpiece...no is like you.
🤟🤟🤟🤟
You are great Sir! Good time going in these days just because of your videos. DP is love and you made it loveable man!!:)
bhai jb sum ban jate hai toh accha lagta hai...confidence aata hai ki merese bhi solve ho sakta hai
Awesome just a small change i.e. t[i] instead of t[i-1] did the whole magic
Thank you for relating the things. which makes it easy to remember and understand things
this playlist is very useful for me , thank you sir 😊😊.
13:12 😅😂🤣bahut prachin problem hai. Next level explaination bro
Sir you are fabulous i never saw anyone explaining problems like you
Oooooohhh bhai.......Angaar lagaa rahe ho tusi! Bus ek chotah se request, 0/1 aur unbounded ke jitne bhi problems hai unke links apne description pe daldena, practice karne ko easy hojata, Buss us question ka nahi, koi aur hatke vaale
bestest way of teaching
Best DP course on internet!
The explaination did not clear how to identify an unbounded knapsack, only thing i could get is that in an unbounded knapsack, the elements can be repeated. please elaborate how would we know to solve a problem with unbounded knapsack as a base?
Will it be mentioned in the question that repetition is allowed?
Yes, I was also thinking how to identify whether a knapsack has to be solved as 0-1 or unbounded, and Aditya didn’t gave any hint about this. According to me, in this question it is mandatory that the length of all the segments has to be equal to the length of the rod (that is N). if we’ll try solving this using 0-1 knapsack, we might not be able to get this condition fulfilled, that is in case of 0-1, there’s a possibility that the length of all the segments maybe or may not be equal to the length of the rod, because in case of 0-1 it can also come out to be less than the length of the rod, which we have seen in 0-1 knapsack problems, that the knapsack is not fully filled sometimes.
In this problem the length of the rod must be equal to the sum of length of all the segments, or you can say that it is a kind of knapsack problem with an extra condition that the knapsack has to be filled completely upto its capacity. By using an element many times we might be able to completely fill the capacity, which is sometimes not possible with 0-1. So try using unbounded in cases where you have to completely fill or where you have to reach the capacity or length or anything given in the problem.
And it is not mentioned in the question, if you'll check on various platforms, its not mentioned there about repetition and all.
I think the code is wrong. In knapsack the total weight of selected items need not be equal to Knapsack capacity. But in this case the total length of selected segments must be equal to Length of the rod not less.
but that doesnt make our code wrong?! that just makes it to be a case where we can fully fill the knapsack always.
@@TheAdityaVerma let's say state is (n, length). Say we are finding (1,9). First element length is also 9 then (1,9) = 1+ (0,0) = 1 and it's correct. But if length is is 7.
(1,9) = 1 + (0,2) and since we have initialised both 1st row & 1st col as 0, (1,9) = 1 but that's wrong since we only have 7 in our array and can't make 9 length
changing the base case is working
@@charan775 why 1+....
@@joshiadvait8 because you include a segment
One of the best explanation ever found , thank you so much
public class rodCutting {
public static void main(String[] args) {
// Define the profits and lengths for each possible rod piece.
int price[] = { 1, 5, 8, 9, 10, 17, 17, 20 }; // Profits associated with rod pieces.
int length[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; // Lengths of corresponding rod pieces.
int n = 8; // Total length of the rod.
// Create a 2D array 'dp' for dynamic programming.
int[][] dp = new int[price.length + 1][n + 1];
// Initialize the first row (no rod pieces) and first column (no length) of 'dp'
// to 0.
for (int i = 0; i < price.length + 1; i++) {
for (int j = 0; j < n + 1; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
}
}
}
// Fill in the 'dp' array to compute the maximum profit using dynamic
// programming.
for (int i = 1; i < price.length + 1; i++) {
for (int j = 1; j < n + 1; j++) {
if (length[i - 1]
Your videos are great. But here i guess it would be better if you emphasized more on approaching the problem from the rod cutting part instead of directly trying to build the code by making the values analogous to the previous question. I.e some more insight into the real problem would be great. By the way great work 👍
instead of taking length array we can take a variable len = n. and replace len[i-1] with i, where 0
can u share code?
@@kapilsingh2816 class Solution{
public:
int cutRod(int price[], int n) {
//code here
// int length[n+1];
// for(int i=0;i
u can even make a paid course .....but please make playlist on competitive programming
it is difficult and we want teacher like you
please brother
great videos !! please also make one video giving us a road map on how to do extra maths required for higher level problems
Very Good Aditya.. really impressed with your hard work .. I know it takes lot of time to make this .. and help everyone .. Really DP looks very easy now.
Thank you very much. You are a genius.
can u say recurse code for these dp problems cause mostly u're going through tabulation method.
please bro more videos on dp in trees and graph from leetcode hard questions. Fabulous Work!!! 🤩👏
can we do this problem with recursion + memoization similar to 0 1 knapsack
Kitna achha padate ho bhaiya aap.. Please greedy bit manipulation or graph ke liye bhi playlist bnado
Great content. Please make videos on graphs and trees. Please.
i love the way you rotate the pen with our fingers :-))
PS: Amazing Explanation.
Your explanations are very much easy to understand.
If possible, can you please make video on choice diagram of rod cutting problem.
12:54
"Ah, I see you're a man of culture as well"
Vs code shortcut ctrl+H replace weight to length, value to price
bhai yr bhot sahi kaam kia hai apne agr aap greedy ya back tracking ki bhi aasi playlist bnado bhot help hogi
The way he relates everything is just awesome😎😎
is problem ko sochne ka najariya hi badal dia aapne,,, thankz
0-1/Fractional/Unbounded knapsack could be filled without reaching the capacity, but in rod cutting you need to reach the capacity (total length). How do you tackle this? @aditya
When you make a cut, u choose the price for that len. The remaining part of the rod is also optimally cut. You sum up these prices -- cur max price = curr len price + 'max' price for remaining len
initialize 0th row by minus infinity(-inf).
@@gokulgopinath3777 Yes it works, but can you explain why??
@@VIVEK1898 if u dont know the array of price and length and rod is given to u then how u can find profit if u dont know the price distribution
@@Kaivalyamani yeh for maximum loss it is -inf
This is really amazing .....Great explanation
4:34 waah kya style hai Pen change karne ka :D :D ;)
Engrave this in stones and history will witness that best ever tutorials created for Dynamic Programming on entire planet was created by Aditya Verma. Period.
If only price array and length as an argument is given then what would be its recursive code without memoization?
In given problem link many are assigning t[0][i]=INT_MIN
Isn't we are talking about length here, how can we take loss?? I didn't get this, ig minimum value can be '0' only, right? then why INT_MIN?
Same question!! Did you figure out later? Aditya's approached worked for me for the given link. I don't understand what's happening here.
@@LearningYouth same here. Tell me if you figure it out.
Best explanation sir !! this video is really really helpful sir !!
please post the link of similar problems from coding various websites, it will be for understanding the topic...BTW your videos are among the best
U deserve a million of blessings
bhaiya yrr ekdum bawaal chiz hai 🔥...ekdum gardaa uda diye😅❤❤
Recursive version. You can do memoization easily.
int cutting_rod(vector price, int length, int cut) {
if (length
what is the difference between size and length? ( during the end when we make table ....for that)
I first thought of a 0/1 knapsack kinda approach where each "n" is --> do you want to cut here or not?
if cut here, store the value, and pass to recursive call (n-1, 0)
if not cut here, increment the value, and pass to recursive call(n-1, value + arr[n-1])
for each n, return max of these 2 values
but that was the wrong approach. though I conceptually didn't get why it was the wrong way...
Given the stock bars of length L=12m (plenty in stock), Lengths to cut = Array(3.5, 4.2, 6.5, 5.7)m, Quantity required = Array(50, 30, 70, 45) nos. To find the minimum number of stock bars required. How to do this? Please advice.
U R THE RESON I DEVELOPED INTEREST IN DSA
in rod cutting how it i related? in unbound we can take less than wt? but in rod can we take as cut less than length?
Epic teaching bhai!!!
" Unbounded Knapsack ek pracheen problem hai " - Aditya Verma [2020].
What does a cell here represent in the table? This one seems confusing. Each column represents length of rope and each row represents what?? Can anyone explain exactly what is the cell at location i,j represents and what is i and what is j there precisely??
Each row represents the length of rod and column represents the size of array . So if we are at dp[i][j], it means that this cell gives solution when the length of rod is j and size of array is i.
For example if array={5,5,2} and length = 7 then the cell dp[3][2] represents a situation in which length of rod is 3 and size of array is 2 i.e elements of array available for this length are {5,5}
This is just a general idea of what dp represents for cell [i][j]
Sir can you explain the cut ribbon problem of codeforces using this technique,I tried to use but it failed
Yeah i'm also stuck with same problem.
He has done the initialization wrong, that is why; And did not correct it yet, like he does not care. Initialise row 0 with -inf.
Sir, on the link that you have mentioned, they have provided all the solutions using O(n) extra space but we are using O(size*N). How can we optimize it to O(N)?
Just use a for loop for length array and an array for storing instead of matrix
yes , it is mentioned that we have to use O(N) auxiliary space, but gfg has accepted my solution even though i've used a matrix. How is this happening?
Amazing work buddy🙌🙌
what is minimize, is that same by replaceing max with min
Minimum cost to cut a stick on leetcode is not unbounded knapsack??
i successfully build the recursive tree my my own but i m confused abut LC hard problem min coast to cut rod is quite different
in this code how we will write the intialisation? how we will fill the table??
but if the size of data, length>=1e4 than the algo will not provide any result because of large dataset. How can we fix it?
There is no need to make an extra Length array, simply traversing from 1 to n in for loop will do the task.
We can solve unbounded knapsack related questions using 1D array too. No need to store the information in 2D array; reduces space complexity.
Can someone post the complete solution of the question given in the description.
how Time can be Linear ??? May be you have mistaken with space because GFG uses 1D array(No need to keep track of items that was inserted or not). and he is using 2D array(Keeping track of items which is redundant). All Unbounded Knapsack problems can be solved by using 1D array. He is maintaining the similarity for viewers so he is not confusing people by trying to give the most optimal approach where solution may differ from one another.
Sir please make a playlist on graph.
In initializing the matrix when size of length array is zero ,then why we are not getting profit equal to total length. And we are initializing first column and row with 0.
your analogies are damn good 😍😍
Great as always Aditya :) But the code in this video is missing a case that sum of lengths of selected segments of rod must be equal to the total length of the rod. This case can be handled by changing the initialization of dp matrix as mentioned below.
for(int i=0; i
how does INT_MIN help with that??? i have trouble visualizing this
Why you initialised the first row with INT_MIN?
kya tarika hai yar padhane ka :) .. amazing
u r amazing man, m in love with dp!
Hi @Aditya Verma and everyone, I have a small confusion and need some help :
There is this question in which array of pieces(size) to be cut from a rod(or ribbon or line segment) is given. and maximum length of rod(or ribbon or line segment) is given. We have to find the maximum number of segments we can make by cutting only of the sizes given.
For example :
max size of rod = 7
pieces allowed to cut = [5, 2, 2] (n = 3 , i.e. size of this array is 3)
Correct Output = 2 (i.e. we can get "two" segments i.e. 5 and 2)
I tried solving it using the approach taught above, i get 3 as my answer and I know somewhere I am going wrong. In case you guys want to see my approach, this is a small segment which explains all : (initialization has been done)
for(int i = 1; i
def fun(a,n):
dp=[[0 for i in range(n+1)] for j in range(4)]
for i in range(1,4):
for j in range(1,n+1):
if j>=a[i-1]:
if dp[i][j-a[i-1]]!=0 or j==a[i-1]:
dp[i][j]=max(dp[i-1][j],1+dp[i][j-a[i-1]])
else:
dp[i][j]=dp[i-1][j]
else:
dp[i][j]=dp[i-1][j]
return dp[-1][-1]
refer this ....,your code is correct but you only have to add one condition (my 6th line).....kyunki agar apan rod ko divide kar rahe hai toh uske saare parts (elements) given array(pieces) mai se hi hone chahiye
@@jimenluhar7126 Thanks a lot brother. Just one thing, I can understand "j == a[i-1]" which means that "piece ka size" should be in the array. But iska matlab kya hua "dp[i][j-a[i-1]]!=0" ?? Can you please explain this ? I will be very thankful
@@codestorywithMIK agr j-a[i-1] not equal to 0 hua... matlab ki apn currently jis piece k liye loop chala rahe h uske bina bhi apni rod valid h (mtlb agar puri rod mai se apan ne a[i-1] element nikal diya toh jo rod bachi hai uski length prices array mai honi chahiye ya fir usko further break kiya ja sakta h !!)
@@codestorywithMIK for example n=7
Pieces=2,2,5
Toh tumhare code k hisaab se 3 cut hone chaiye jisse 3 elements ki length 2 hogi aur aik ki 1 (2+2+2+1=7) but jo rod ka element h uski length 1 nahi ho sakti kyunki woh pieces array mai nahi h !! mtlb correct answer 2 cut h (2+5) jo valid hai
@@codestorywithMIK agar dp[i-1][j-a[i-1]] equal to 0 hua matlab ki j-a[i-1]. ko apan valid nahi bol sakte kyunki woh pieces array mai bhi nahi hoga aur usko pieces array k elements use karke bhi break nahi kiya ja sakta (use element ko apan ne pehle hi process kar liye h ).
can we solve it using partition DP ?
Solved at 3:00, Thanks Man
@Aditya Verma What are the sources from where we can have hands-on on this topic.Your videos are worth watching but having a hands-on would surely clear all the doubts i guess!
do practice at geeksforgeeks portal, all questions are available there
atcoder.jp/contests/dp/tasks this is a complete list of DP problems, here you can practice more. (I think after watching Aditya's videos you can do all of them ).
Same to Same question was asked in Cognizant GenC Next Online Coding Round.
Please suggest some good playlist/channel for
1. Graph
2. Mathematics questions
A good teacher but sir thoda try to make video faster 1 baat again and again
i did it the same way still wrong answers are coming every time. can you pls help
please explain how to reduce space complexity from O(n2) to O(n)
It's really hard to explain anything over text, will try to make a video, till then you can find articles about it. Thanks for watching brother !!
can i get the notes of urs ?? Softcopy///pdf///
I really dont have one with me rn.
nice explanation
Waiting for bhai ke 30k subscribers hone ka :)