One day your juniors of NIT Bhopal will be proud to have a senior who could teach programming concepts in such a beautiful way! Keep going, love the content.
Great work brother, u are like the interviewbit of teaching , u have the crux of everything and complete understanding of what u r teaching!!. Hats Off..
To pass all corner cases, we should correct "if statement". Runnable code: Python code, dp=[[0 for j in range(sum+1)]for i in range(n+1)] for i in range(n+1): for j in range(sum+1): if j>0 and i==0: #corrected line j should be greater than 0, j>0. dp[i][sum]==False elif j==0: dp[i][j]=True elif arr[i-1]
Thanks brother !! Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
Friends explanation for quick exam prep....remembering all friends who are just bright and sharp as you who would help a friend in need....Superb explanation.....never fell asleep even if your video is long. The power of your explanation is superb....keep it up. hope to see more from you a lot more!!!
after watching his videos it feels like I can achieve Nirvana 😅. I get so much peace after understanding the concepts because he teaches so damn well!!
I just blindly followed your logic and method to convert the recursive code to tabulation version and it worked without even testing it manually. I had automated tests written to verify. Thanks for sharing your knowledge 🙏🏽
speak sach only People from your family go to Vaishnodevi and cry in a bhawan while chanting Mata bhajan and when you and your family come back to hometown you people start doing fraud and do dhokhebaazi in business and eat money of poor people Do remember mata is watching everything your crocodile tears in bhawan vaishno Devi and your bad deeds in your business and in some other place
this guy is just GOD OF DP!!!! prev video dekha n problem explanation se hi khud se recursive and top down bna liya! I wish hmare teacher aisa pdha pate!!!!!!
Note to myself : We have to decrease the number of elements by 1 in both Inclusion and exclusion! Inclusion means, we take current element and start to identify the possible solutions for the remaining sum with rest of the elements! Exclusion means, we discard the current element and start to identify the possible solutions for the same sum with rest of the elements excluding the current one!
Best video with so much ease...teaching style is awesome. I saw Tushar Roy's video for same problem. There is no comparison with this video. Accent and language doesn't make problems seem easy :)
To understand why that "max" was changed into Boolean OR operation: Once you write the recursive solution, you will observe that when arr[n-1] is less than or equal to the subset sum, the subset sum can be found in the array (i.e. we return true) in either of the following cases: 1. a. If the (subset sum - arr[n-1]) can be found in the first n-1 elements of the array (Including arr[n-1] in subset) 1. b. If the subset sum can be found in first n-1 elements of the array (Not including arr[n-1] in the subset) So we return Boolean OR of the two above give conditions return subsetSum(arr, n-1, sum-arr[n-1]) || subsetSum(arr, n-1, sum))
@TheAdityaVerma, I loved the way you put your thoughts. Great effort. This code allows to take each number multiple times. For input array {2, 5} and target sum=90 your code returns true. We should either change the problem statement to call it unbounded or fix the code to take each number only one time. One way to fix code is take t[i-1][j-arr[i-1]]. i.e. Corrected code: t[i][j] = t[i-1][j-arr[i-1]] || t[i-1][j]; Your code: t[i][j] = t[i][j-arr[i-1]] || t[i-1][j];
In description of this video , where u give example "Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9 Output: True //There is a subset (4, 5) with sum 9", here , subset {3,4,2} is missing which also gives the sum 9. btw, your content is too op.
If you do max as for Knapsack it will be same logically, as Max for two booleans is same as Max. 1 or 1 is same as Max(1,1), 1 or 0 is same as Max(1,0) and 0 or 0 is same as Max(0,0)
bhaiya me sach me comment nahi karta zada par kasam se bhaiya yar bhut acha playlist banaya hai meko bhut kuch pata chala apki vedios seee me electronics ka student hu apne mere zindagi bana dii bhut achi vedio god blesss you
1 suggestion in Knapsack: When you are processing i-th element, you can create variable iterVal = val[i-1] and iterWeight = wt[i-1] and use these variables in the max expression. This will help in better understanding the concept as well as look less scary & more readable: max(iterVal + t[i-1][j - iterWeight] , ...)
I don't who & why people disliked the videos.. These videos & concepts are outstanding.. Aditya Verma u made DP easy for me :P Thanks alot for such content.
I tried to solve this problem without watching this video using recursion with memoization and it felt like a cake walk. Recursion has never been so easy to me. Thanks mate. I would like to buy a coffee for you. Do you have a patreaon link or something similar ?
I don't have any word to tell about your explaination technique b/c it is amazing keep it up bhaiya .The way you explain the question,i easily write the code without your seeing your code.
aapka channel milne se pahle DP se darr lg rha tha but ab total darr khatm... thanks for explaining in very easy way that even below average student can also understand... Best wishes
Hi, I'm watching the first 3 videos you teach about dynamic programming. Lectures are very good and easy to understand. However, my English level is limited. I hope you can turn on the subtitles in the next videos so that I can easily understand the article. Thank you very much!
i 'm watching his video and then tushar's video to get a clear undrstanding this video is good for basics and then check tushar's video to see how the table gets populated (if you have doubt on the table population )
Great explanation but it would have been great, if you could have started with Memorization and then proceed with top down . Anyway i have referred the comments of the people , who had given Memorization solution but couldnt understand that why everyone is using 2D memorization array whereas this problem could be solved with 1D array , the similar 1D approach we take in Fibonacci. Here is my Memorization solution using 1D, and would appreciate if you could help me to optimize if its applicable. public class DynamicProgramming { static int arr[]={2,3,7,8,10}; static int sum=24; static int[] mem =new int[arr.length+1]; static int isSubset(int arr[], int sum, int n){ if (mem[n] != -1) { return mem[n]; } else{ if (sum == 0) return 0; else if (n == 0) return 1; else{ if (isSubset(arr, sum - arr[n-1], n-1) == 0|| isSubset(arr, sum , n-1) == 0){ mem[n]=0; } return mem[n]; } } } public static void main(String[] args) { for (int i=0;i
I don't have words to thank you bhaiya, since itna accha to teachers rupee le kar bhi nhi pdhate jitni acchi education ap hmre lye de rhe ho, big thanks🤗
For anyone wondering why do we perform OR in place of MAX operation is because --> here we need to see if "ANY" combination of the array elements in the subset can sum up to the current target. If I found that 1 out of 10 subsets sum up to the current target then I can say it's TRUE even if the rest 9 subsets don't satisfy because I just need one.
your initialization logic in both knap sack and here is costlt O(n*w) which however can be done in O(n + W) The whole point of DP is to reduce time complexity so I think we should do the same wherever possible
Hello Aditya, you are thousands of us from this series. There is just a small correction in this code , since it does not consider the case of negative elements. If we have arrray = {-3,-2,5,7} and sum = 2 then ,because we are ignoring the elements greater then sum it wont consider 5 -3 =2 and will return false. Correct me if I am wrong
Nice explanation... I used different approach... I solved this as binary knapsack and because values of weights are not given , i took weight as value, then to check subset sum if t[n][sum]== sum then true, otherwise false
Hi Aditya, need a help with the below question. Samu is playing a shooting game in play station. There are two apples to aim in this shooting game. Hitting the first apple will provide her X points and hitting the second apple will provide her Y points. And if she misses the apple she chose to hit, she won’t get any point. Now she is having N coins and each shoot will cost her 1 coin and she needs to score at least W points to win the game. Samu don't like to lose at any cost. At each turn, she has two choices. The choices include: - Hitting first apple with probability P1 percent. However, she might miss it with probability (1-P1) percentage. Hitting second apple with probability P2 percent. However, she might miss it with probability (1-P2) percentage. She would like to know what is the maximal expected probability (as a percentage b/w 0 and 100) of winning the shooting game. Note: Choosing to hit any apple is entirely her choice. Both are independent events meaning P1 + P2 may/may not exceed 100. Output must contain 6 digits after decimal.
This is the cpp tabulation code: In this lecture, it got accidently skipped but we have to use dp[i-1][j-arr[i-1]] instead of dp[i][j-arr[i-1]], watch the knapsack tabulation for more clarity. class Solution{ public: int subset_tabulation(vector&arr,int sum){ if(arr.size()==0 and sum!=0) return 0; if(sum==0) return 1; vector dp (arr.size()+1,vector(sum+1)); for(int i=0;i
Amazing playlist so far! The style of teaching the techniques rather than just the answer is awesome! Directly writing the bottom up solution feels tough though - when writing the code should we start with the recursive solution first and then convert it to bottom up as explained in prev videos?
according to me, the memoization can not be performed normally in this question since there can only be 2 values in the memoized array i.e. true or false, so when initializing that memoized array with some value (such as initializing -1 in all cells of array in knapsack), we can not just initialize the array with either true or false since that does not ensure that whether the problem for that cell is solved before or not. Correct me if I am wrong.
@@nishantsethix Yes true, I think the initial value in that case can be -1, or if you are using java, can use Boolean class since the initial value it contains is null.
Your explanation is speechless!!, I only have one small doubt, in the beginning of the playlist, we were told that we can apply dp to those problems which usually have two properties, first overlapping sub-problem and second is optimality. I'm not able to grasp if this problem is asking for any optimal solution, that is largest, longest, min, max, etc...can someone tell me if it's asking for any optimal output...or if it is not, then what about these two mandatory properties??
Sir, i am sure you are a very busy person but i tried all channels and honestly given this covid only you can help us in securing a job. It's a humble request please keep making videos. You are my last hope for getting a grasp at algos please.
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.
May is near so can you tell exactly when are you going to upload the videos and on which topic . So that I won't learn those topics right now from other TH-camrs (waste of time + energy) . When are you going to complete this playlist of DP. ?
Sir just for confirmation - 20:58 me t [ i - 1 ] hona chahiye na(Because we have processed the last element)?
Yes yes of course, thats just a typo !! Wait here let me pin your comment to help others !!
This playlist is really helpful.Thanks Sir.
@@TheAdityaVerma Hey, You can add correction in the video as a popup. Great Work Anyways.
@@harshitanand8216 i will always start from 1 since we already did the initialization for i = 0
Thanks Keerat! Wohi soch raha tha
Watched all the ads just to support you! I usually have ad blocker. You are killing it!
Purushhottam Prashant hai bhai tu 🙏 jokes asides, Thanks a lot brother, this world really don't have many people like you :D 🙏
@@TheAdityaVerma 🤣🤣🤣🤣🤣🤣
@Saswat Pattnaik uBlock Origin Chrome Extension.
Better buy a youtube premium
@@ScienceSeekho better use another browser where there are no ads for any type of content
Mind blowing explanation, I usually do not comment but this sort of material needs a big applaud.
if you got placed now,please refer me
@@raunop8208 koi ni hota refere bhai padhleeee
@@raunop8208 experience se bata raha hu
@@raunop8208 She in Microsoft bro
@@raunop8208 bhai Teri lag gyi to hume refer krde ab XD
7 of 50 (14%) done! Very nice explanation of initialization and the summary at the end was a great wrap-up, tying everything together.
One day your juniors of NIT Bhopal will be proud to have a senior who could teach programming concepts in such a beautiful way! Keep going, love the content.
But I think he is from MNNIIT Alahabad
@@PalakMittal NIT ; )
@@ananypandey1310 Yeh! My bad 😅
@@PalakMittal No, he is from MANIT Bhopal
I"ve done course from coding ninjas but this playlist makes me understand dp easily , serioulsy you are an inspiration
Thanks for the advice.Gonna complete dp from here and then go back to that course.
bhai agr teri videos aj se 1 month phle mil jati dp ki too life set ho jati. Very good job dude. I think tushar roy should learn something from you.
Thanks a lot brother, Please share the content so the same doesn't happens to others and these videos get to them in time before interviews.
bhai tushar roy ke video tab k hai jab .....koi itne video nhi hua krte the...isliye usko pta nhi hai ki viewers kya chahte hai..
Great work brother, u are like the interviewbit of teaching , u have the crux of everything and complete understanding of what u r teaching!!. Hats Off..
So nice of you !! Thanks was really a creative compliment 😂✌️
@@TheAdityaVerma link g4g you attached is slightly different , aint it ?
Your videos helped me a lot to grasp the concept of DP . Cannot thank you enough for this precious content that you make. Keep teaching brother .
To pass all corner cases, we should correct "if statement".
Runnable code:
Python code,
dp=[[0 for j in range(sum+1)]for i in range(n+1)]
for i in range(n+1):
for j in range(sum+1):
if j>0 and i==0: #corrected line j should be greater than 0, j>0.
dp[i][sum]==False
elif j==0:
dp[i][j]=True
elif arr[i-1]
my code failed exactly in that case and im glad that someone mentioned like u mentioned the corrected one
Soon your playlist will come in the top 10 , best wishes. I just want you to add more videos on Algorithm :)
Thanks brother !! Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
@@TheAdityaVerma How is your job going. You mentioned in previous video that you got 16L package.
So many institutes will fail to explain like this. Hats off to you
Friends explanation for quick exam prep....remembering all friends who are just bright and sharp as you who would help a friend in need....Superb explanation.....never fell asleep even if your video is long. The power of your explanation is superb....keep it up. hope to see more from you a lot more!!!
Best channel on youtube . On my way to finish the dp playlist
after watching his videos it feels like I can achieve Nirvana 😅.
I get so much peace after understanding the concepts because he teaches so damn well!!
But it doesn't pass all the testcase
@@yatri6329 whats the problem?
I might help
I just blindly followed your logic and method to convert the recursive code to tabulation version and it worked without even testing it manually. I had automated tests written to verify. Thanks for sharing your knowledge 🙏🏽
You are awesome man! I never had imagined that I will be able to solve DP problems but I can now, all thanks to you. Keep on this amazing work :)
speak sach only
People from your family go to Vaishnodevi and cry in a bhawan while chanting Mata bhajan and when you and your family come back to hometown you people start doing fraud and do dhokhebaazi in business and eat money of poor people
Do remember mata is watching everything your crocodile tears in bhawan vaishno Devi and your bad deeds in your business and in some other place
@@arch3994 wtf
@@arch3994 lmao
this guy is just GOD OF DP!!!! prev video dekha n problem explanation se hi khud se recursive and top down bna liya! I wish hmare teacher aisa pdha pate!!!!!!
This is genuinely the GOD level explanation !! Thanks Bro
Undoubtedly the best playlist on DP (I didn't go through the comment section and then re-watched previous videos to see if I missed a concept. LOL)
Note to myself : We have to decrease the number of elements by 1 in both Inclusion and exclusion! Inclusion means, we take current element and start to identify the possible solutions for the remaining sum with rest of the elements!
Exclusion means, we discard the current element and start to identify the possible solutions for the same sum with rest of the elements excluding the current one!
Really very helpful . I don't know how many times I have come back to re-watch this playlist.
great work brother. Kahi ni mili esi understanding, jitni teri basic videos se mil gayi. Thanks
Mast Padhaya Bhai Dil Khush ho gaya Dekh kar, Khud se ab problem solve kara to maja hi kuch aur tha concept mst clear kara bhai !!!
Thanks Brother !! Do share where ever you feel right to help the channel grow !!
The best video ever on dp..The way you are teaching....Is just amazing
Solved my first DP question after watching your tutorials. Huge Thanks bro!
Kudos to u brother.
I too hv solved my first Dp problem 2 days back..
I knw this feeling man.
Best teacher ever... Thanku for helping all of us..
I loved the way you explain and keep focusing on the details again and again to make it stick, but a dry run with any example would've been better.
I was able to initialise dp array by using recursion. No one tells this thing is comming from recursion base condn. Great work man.
The best explanation in the youtube on DP where I found the explanation even in Matrix wise ,where no one does..
Solved this without even seeing the video. Knapsack explanation🔥🔥🔥🔥
nobel prize
love your videos. If you did not made this playlist I might have never understood DP.
Best video with so much ease...teaching style is awesome. I saw Tushar Roy's video for same problem. There is no comparison with this video. Accent and language doesn't make problems seem easy :)
Haha Thanks Archana !! I love his accent tho 😂😂😂😂I mean who doesn't right? 😅
@@TheAdityaVerma but you teach as a elder brother or a friend ...
@@TheAdityaVerma thank u
How to select which term to take as row and column....
What if we take vice versa???
To understand why that "max" was changed into Boolean OR operation:
Once you write the recursive solution, you will observe that when arr[n-1] is less than or equal to the subset sum, the subset sum can be found in the array (i.e. we return true) in either of the following cases:
1. a. If the (subset sum - arr[n-1]) can be found in the first n-1 elements of the array (Including arr[n-1] in subset)
1. b. If the subset sum can be found in first n-1 elements of the array (Not including arr[n-1] in the subset)
So we return Boolean OR of the two above give conditions
return subsetSum(arr, n-1, sum-arr[n-1]) || subsetSum(arr, n-1, sum))
Can you Post the recursive code solution ! Thanks
@@AbsolutePainyeah, here you go:
bool isSubsetSum(int arr[], int n, int sum){
if(n==0) return 0;
if(sum == 0) return 1;
if(arr[n-1]
videos dekh kr apki mn krta hai bs dekhte hi jao....best person
ye to kuch kuch 5- start jese ho gya - "khao aur kho jao" 😂😂
bhai tu meri zindagi ka pehla aur iklauta pyaar hai. Tere channel ko meri duaein lage. Lagni zaroori bhi hai, mai heejda hu
Aditya, I am not exagerating. You truly deserve the Dronacharya award had they been giving it for academics.
@TheAdityaVerma, I loved the way you put your thoughts. Great effort.
This code allows to take each number multiple times. For input array {2, 5} and target sum=90 your code returns true. We should either change the problem statement to call it unbounded or fix the code to take each number only one time.
One way to fix code is take t[i-1][j-arr[i-1]]. i.e.
Corrected code: t[i][j] = t[i-1][j-arr[i-1]] || t[i-1][j];
Your code: t[i][j] = t[i][j-arr[i-1]] || t[i-1][j];
At last found someone who noticed. Thank you for your answer. Can you explain how the corrected code works. I couldn't get it
I saw many dp videos, so far this one is the best. Thanks for such great explanation. Keep posting such videos!
In description of this video , where u give example "Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True //There is a subset (4, 5) with sum 9", here , subset {3,4,2} is missing which also gives the sum 9. btw, your content is too op.
If you do max as for Knapsack it will be same logically, as Max for two booleans is same as Max. 1 or 1 is same as Max(1,1), 1 or 0 is same as Max(1,0) and 0 or 0 is same as Max(0,0)
I can't believe I am able to solve this problem by own 😊😊😍thank you😊 for clearing concepts and give a way to how to approach
In which language u code??
Bhaiya teacher ho to aapke jaisa !! Maza aa gya !! 😁
Yaar!!!!. Ek he toh dil hai kitne baar jitoge.
bhaiya me sach me comment nahi karta zada par kasam se bhaiya yar bhut acha playlist banaya hai meko bhut kuch pata chala apki vedios seee me electronics ka student hu apne mere zindagi bana dii bhut achi vedio god blesss you
1 suggestion in Knapsack:
When you are processing i-th element, you can create variable iterVal = val[i-1] and iterWeight = wt[i-1] and use these variables in the max expression. This will help in better understanding the concept as well as look less scary & more readable:
max(iterVal + t[i-1][j - iterWeight] , ...)
sahi baat mere coder!!
nobel prize laya jae bhai k liye😪😐😐
u r best bro.. i have learnt from many youtubers but you and traversay media are best .. ur basic is clear..
Completed 7 out 49 video....I will comment upto lecture 35 ., today on every video for sure..
thank you for making this excellent video!! We all are grateful to you! Soon I will get a good job. Thanks to you!!
I am a GSOCian but my advanced CP isn't good enough...This is really helpful....Thanks a lot @Aditya Verma :)
You are doing a great job bhaiya....God bless you..
This was a really nice explanation. I was stuck in this from a day , couldnt relate. Thanks 😁 please keep making videos
Thanks !! I am glad it helped you !! Do share and subscribe.
@@TheAdityaVerma bhai aap legend ho please video banao aur
I don't who & why people disliked the videos.. These videos & concepts are outstanding.. Aditya Verma u made DP easy for me :P Thanks alot for such content.
they don't like to understand things
I tried to solve this problem without watching this video using recursion with memoization and it felt like a cake walk.
Recursion has never been so easy to me.
Thanks mate.
I would like to buy a coffee for you. Do you have a patreaon link or something similar ?
Yes he has patreon now, check new videos for link.
@@MALIWAL1000 yes, already a member
have you got TLE with memoization?
I don't have any word to tell about your explaination technique b/c it is amazing keep it up bhaiya .The way you explain the question,i easily write the code without your seeing your code.
aapka channel milne se pahle DP se darr lg rha tha but ab total darr khatm...
thanks for explaining in very easy way that even below average student can also understand...
Best wishes
Bro please make videos on tree also ...🙏🏻🙏🏻it will be helpful for my interview....make all videos on trees
It would be really nice if you can dry one problem at the end of the video. Keep the good work going!
Sir your way of teaching is just great. I don't have words to thank you🙏🏻🙏🏻🙏🏻🙏🏻
Aditya Verma, Nice explanation, If you could dry run your inputs and show the output right there, it will be a bit easier to understand
Best explanation watched on fractional knapsack based problem solving using DP 🤩🙌❤️
Hi, I'm watching the first 3 videos you teach about dynamic programming. Lectures are very good and easy to understand. However, my English level is limited. I hope you can turn on the subtitles in the next videos so that I can easily understand the article. Thank you very much!
i 'm watching his video and then tushar's video to get a clear undrstanding
this video is good for basics and then check tushar's video to see how the table gets populated (if you have doubt on the table population )
yeah. No explanation of how the solution is being written atleast.
Great explanation but it would have been great, if you could have started with Memorization and then proceed with top down .
Anyway i have referred the comments of the people , who had given Memorization solution but couldnt understand that why everyone is using 2D memorization array whereas this problem could be solved with 1D array , the similar 1D approach we take in Fibonacci.
Here is my Memorization solution using 1D, and would appreciate if you could help me to optimize if its applicable.
public class DynamicProgramming {
static int arr[]={2,3,7,8,10};
static int sum=24;
static int[] mem =new int[arr.length+1];
static int isSubset(int arr[], int sum, int n){
if (mem[n] != -1) {
return mem[n];
}
else{
if (sum == 0) return 0;
else if (n == 0) return 1;
else{
if (isSubset(arr, sum - arr[n-1], n-1) == 0|| isSubset(arr, sum , n-1) == 0){
mem[n]=0;
}
return mem[n];
}
}
}
public static void main(String[] args) {
for (int i=0;i
the similarities are explained greatly brother, thanks for your effort🙏
I don't have words to thank you bhaiya, since itna accha to teachers rupee le kar bhi nhi pdhate jitni acchi education ap hmre lye de rhe ho, big thanks🤗
Thanks sir ,because of these video, grasping concepts of Dp become easy.
For anyone wondering why do we perform OR in place of MAX operation is because --> here we need to see if "ANY" combination of the array elements in the subset can sum up to the current target. If I found that 1 out of 10 subsets sum up to the current target then I can say it's TRUE even if the rest 9 subsets don't satisfy because I just need one.
your initialization logic in both knap sack and here is costlt O(n*w) which however can be done in O(n + W)
The whole point of DP is to reduce time complexity so I think we should do the same wherever possible
Hello Aditya, you are thousands of us from this series. There is just a small correction in this code , since it does not consider the case of negative elements. If we have arrray = {-3,-2,5,7} and sum = 2 then ,because we are ignoring the elements greater then sum it wont consider 5 -3 =2 and will return false. Correct me if I am wrong
Nice explanation... I used different approach... I solved this as binary knapsack and because values of weights are not given , i took weight as value, then to check subset sum if t[n][sum]== sum then true, otherwise false
@Aditya Verma how to print all the subset after we create the matrix....... ??
take a global list and fill that once you reach the answer
@@HarshitGupta005 how we can fill
Literally thanks a lot from the bottom of my heart
mazaa aagaya bhaiya... aag laga diye.... iit-jee k coaching k din yaad aagaye.
One of the Best tuturial>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Hi Aditya, need a help with the below question.
Samu is playing a shooting game in play station. There are two apples to aim in this shooting game. Hitting the first apple will provide her X points and hitting the second apple will provide her Y points. And if she misses the apple she chose to hit, she won’t get any point.
Now she is having N coins and each shoot will cost her 1 coin and she needs to score at least W points to win the game.
Samu don't like to lose at any cost. At each turn, she has two choices. The choices include: -
Hitting first apple with probability P1 percent. However, she might miss it with probability (1-P1) percentage.
Hitting second apple with probability P2 percent. However, she might miss it with probability (1-P2) percentage.
She would like to know what is the maximal expected probability (as a percentage b/w 0 and 100) of winning the shooting game.
Note:
Choosing to hit any apple is entirely her choice. Both are independent events meaning P1 + P2 may/may not exceed 100.
Output must contain 6 digits after decimal.
Amazing👌 How did you develop this level of thought process and clarity?
Like the concept of linking the new problems to classical ones.
Great playlist. Thank you!
Sir your videos are very helpful and your explanation is amazing please continue to upload such amazing videos thank you so much !!
This is the cpp tabulation code:
In this lecture, it got accidently skipped but we have to use dp[i-1][j-arr[i-1]] instead of dp[i][j-arr[i-1]], watch the knapsack tabulation for more clarity.
class Solution{
public:
int subset_tabulation(vector&arr,int sum){
if(arr.size()==0 and sum!=0) return 0;
if(sum==0) return 1;
vector dp (arr.size()+1,vector(sum+1));
for(int i=0;i
i think for this question recursion is more efficent, we just return where we find true and not recurse further.
i just wish i was idian to understant what he is saying i get the idea but just wanted to understant directly the video neverless great job man
JUST A REQUEST NEVER STOP UPLOADING KCH BHI KOI BHI TOPIC CHLEGA !!!!!! the way u make us understand things are amazing!!!
Amazing playlist so far! The style of teaching the techniques rather than just the answer is awesome!
Directly writing the bottom up solution feels tough though - when writing the code should we start with the recursive solution first and then convert it to bottom up as explained in prev videos?
Yes , i wrote the recursive function first , and then memoized it, and then I went on to write the actual iterative code
@@kirtikhohal3313 bool solve(int n,int sum,vector&arr)
{
if(n==-1 && sum==0)return true;
else if(n==-1 && sum!=0)return false;
else if(n!=-1 && sum==0)return true;
else
{
if(arr[n]
yes, I agree with this. Starting from a recursive solution seems more understandable and good in an interview.
according to me, the memoization can not be performed normally in this question since there can only be 2 values in the memoized array i.e. true or false, so when initializing that memoized array with some value (such as initializing -1 in all cells of array in knapsack), we can not just initialize the array with either true or false since that does not ensure that whether the problem for that cell is solved before or not. Correct me if I am wrong.
Instead of appending True or false, you could append 1 or 0. Then before returning you could but a check and return accordingy. (Ik I am late :P)
@@nishantsethix Yes true, I think the initial value in that case can be -1, or if you are using java, can use Boolean class since the initial value it contains is null.
Your explanation is speechless!!, I only have one small doubt, in the beginning of the playlist, we were told that we can apply dp to those problems which usually have two properties, first overlapping sub-problem and second is optimality. I'm not able to grasp if this problem is asking for any optimal solution, that is largest, longest, min, max, etc...can someone tell me if it's asking for any optimal output...or if it is not, then what about these two mandatory properties??
@@KazHachiOreki Sorry, but your explanation doesn't answer my question.
Sir you are great than you so much...you made DP so much fun to solve...Thank you....More videos sir....PLZ...U r amazing
So good. Could you please add a video on printing the subset. There are solns over different sites but would like one here
Sir, i am sure you are a very busy person but i tried all channels and honestly given this covid only you can help us in securing a job. It's a humble request please keep making videos. You are my last hope for getting a grasp at algos please.
Your videos are very helpful. Thank you. Please make videos on trees and graphs as well.
should i try to solve tabulation problems using recursion + memoization to better understand dp??
suggestions??
Awesome explanation.❤️🔥🔥🔥
Doing great job 🙏🙏🙌🙌.
Thank you sir 🤩🙏🙏.
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.
May is near so can you tell exactly when are you going to upload the videos and on which topic . So that I won't learn those topics right now from other TH-camrs (waste of time + energy) .
When are you going to complete this playlist of DP. ?
Great work brother. Thanks for the playlist.
Great explanation, but wondering if it would be more clearer if the solution at the end was explained with on example, how exactly it would work
Can you explain me with
one proper example?
if you have understood considering u saw this 7 months ago.
table bhi optimised way me banai hai waah n/2. true coder
Please keep uploading all the topics of ds algo and we will never look anywhere else on youtube 💓
Awesome explanation sir!
Sir please add recursive + memoization approach for this and subsequent problems🙏🙏🙏🙏