Sir just for confirmation - 20:58 me t [ i - 1 ] hona chahiye na(Because we have processed the last element)?
@TheAdityaVerma4 жыл бұрын
Yes yes of course, thats just a typo !! Wait here let me pin your comment to help others !!
@keeratsachdeva53594 жыл бұрын
This playlist is really helpful.Thanks Sir.
@nirmitsrivastava4 жыл бұрын
@@TheAdityaVerma Hey, You can add correction in the video as a popup. Great Work Anyways.
@manishrawat66784 жыл бұрын
@@harshitanand8216 i will always start from 1 since we already did the initialization for i = 0
@vivekojha48074 жыл бұрын
Thanks Keerat! Wohi soch raha tha
@PrashantSedhainOfficial3 жыл бұрын
Watched all the ads just to support you! I usually have ad blocker. You are killing it!
@TheAdityaVerma3 жыл бұрын
Purushhottam Prashant hai bhai tu 🙏 jokes asides, Thanks a lot brother, this world really don't have many people like you :D 🙏
@aakashgarg83523 жыл бұрын
@@TheAdityaVerma 🤣🤣🤣🤣🤣🤣
@PrashantSedhainOfficial2 жыл бұрын
@Saswat Pattnaik uBlock Origin Chrome Extension.
@ScienceSeekho2 жыл бұрын
Better buy a youtube premium
@ishwarshelke1282 жыл бұрын
@@ScienceSeekho better use another browser where there are no ads for any type of content
@savithalakshmanan28424 жыл бұрын
Mind blowing explanation, I usually do not comment but this sort of material needs a big applaud.
@raunop82082 жыл бұрын
if you got placed now,please refer me
@chatpapdi82252 жыл бұрын
@@raunop8208 koi ni hota refere bhai padhleeee
@chatpapdi82252 жыл бұрын
@@raunop8208 experience se bata raha hu
@riteshMusk4 ай бұрын
@@raunop8208 She in Microsoft bro
@0anant04 жыл бұрын
7 of 50 (14%) done! Very nice explanation of initialization and the summary at the end was a great wrap-up, tying everything together.
@bodlahruthik57304 жыл бұрын
I"ve done course from coding ninjas but this playlist makes me understand dp easily , serioulsy you are an inspiration
@anuragjana1113 жыл бұрын
Thanks for the advice.Gonna complete dp from here and then go back to that course.
@basharatsaigal98003 жыл бұрын
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.
@PalakMittal3 жыл бұрын
But I think he is from MNNIIT Alahabad
@ananypandey13102 жыл бұрын
@@PalakMittal NIT ; )
@PalakMittal2 жыл бұрын
@@ananypandey1310 Yeh! My bad 😅
@suryanshuverma69082 жыл бұрын
@@PalakMittal No, he is from MANIT Bhopal
@siddhartharora15974 жыл бұрын
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..
@TheAdityaVerma4 жыл бұрын
So nice of you !! Thanks was really a creative compliment 😂✌️
@ramupadhya81554 жыл бұрын
@@TheAdityaVerma link g4g you attached is slightly different , aint it ?
@shubham2774 жыл бұрын
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.
@TheAdityaVerma4 жыл бұрын
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.
@starc7014 жыл бұрын
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..
@teetanrobotics53634 жыл бұрын
Best channel on youtube . On my way to finish the dp playlist
@harshavardhankanoj60212 жыл бұрын
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]
@chandakaBalaji Жыл бұрын
my code failed exactly in that case and im glad that someone mentioned like u mentioned the corrected one
@tanmaymalhotra44503 жыл бұрын
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 .
@MohitKumar-sd3ld3 жыл бұрын
So many institutes will fail to explain like this. Hats off to you
@lokeshgoyal9419 Жыл бұрын
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!
@gamerhu74623 жыл бұрын
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!!!!!!
@mridulgoyal34304 жыл бұрын
This is genuinely the GOD level explanation !! Thanks Bro
@amitkumarsingh54144 жыл бұрын
Soon your playlist will come in the top 10 , best wishes. I just want you to add more videos on Algorithm :)
@TheAdityaVerma4 жыл бұрын
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 !! ✌️❤️
@a.yashwanth4 жыл бұрын
@@TheAdityaVerma How is your job going. You mentioned in previous video that you got 16L package.
@SuperSuneel4 жыл бұрын
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!!!
@kajalmishra73674 жыл бұрын
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 :)
@arch39942 жыл бұрын
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
@_aka5h2 жыл бұрын
@@arch3994 wtf
@rishabhinc2936 Жыл бұрын
@@arch3994 lmao
@rohitchatterjee52984 жыл бұрын
Best teacher ever... Thanku for helping all of us..
@akshitmittal125110 ай бұрын
great work brother. Kahi ni mili esi understanding, jitni teri basic videos se mil gayi. Thanks
@riteshpuj95662 жыл бұрын
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 🙏🏽
@accepted58564 жыл бұрын
The best video ever on dp..The way you are teaching....Is just amazing
@asthamishra2877 ай бұрын
Really very helpful . I don't know how many times I have come back to re-watch this playlist.
@yashshukla12564 жыл бұрын
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 !!!
@TheAdityaVerma4 жыл бұрын
Thanks Brother !! Do share where ever you feel right to help the channel grow !!
@harshitasingh9633 жыл бұрын
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)
@sleepypanda71723 жыл бұрын
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!!
@yatri63292 жыл бұрын
But it doesn't pass all the testcase
@Shourya_performs2 жыл бұрын
@@yatri6329 whats the problem? I might help
@punitsharma97032 жыл бұрын
Solved my first DP question after watching your tutorials. Huge Thanks bro!
@Shourya_performs2 жыл бұрын
Kudos to u brother. I too hv solved my first Dp problem 2 days back.. I knw this feeling man.
@danushbasanaboyina13065 ай бұрын
The best explanation in the youtube on DP where I found the explanation even in Matrix wise ,where no one does..
@ASHISHKUMAR-jh9kw2 жыл бұрын
I was able to initialise dp array by using recursion. No one tells this thing is comming from recursion base condn. Great work man.
@mansigoyal34404 жыл бұрын
videos dekh kr apki mn krta hai bs dekhte hi jao....best person
@TheAdityaVerma4 жыл бұрын
ye to kuch kuch 5- start jese ho gya - "khao aur kho jao" 😂😂
@eyeamkd2 жыл бұрын
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.
@hiteshmitruka64193 жыл бұрын
Solved this without even seeing the video. Knapsack explanation🔥🔥🔥🔥
@sahil10532 жыл бұрын
nobel prize
@satya_k2 жыл бұрын
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))
@AbsolutePain2 жыл бұрын
Can you Post the recursive code solution ! Thanks
@satya_k2 жыл бұрын
@@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]
@tusharjajodia90773 жыл бұрын
Yaar!!!!. Ek he toh dil hai kitne baar jitoge.
@arunkranchi4 жыл бұрын
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)
@musicfan16954 жыл бұрын
bhai tu meri zindagi ka pehla aur iklauta pyaar hai. Tere channel ko meri duaein lage. Lagni zaroori bhi hai, mai heejda hu
@PawanKumar-it7np Жыл бұрын
Bhaiya teacher ho to aapke jaisa !! Maza aa gya !! 😁
@sachinmagdum Жыл бұрын
@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];
@SauravKumar-bp4jj29 күн бұрын
At last found someone who noticed. Thank you for your answer. Can you explain how the corrected code works. I couldn't get it
@archanasingh36434 жыл бұрын
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 :)
@TheAdityaVerma4 жыл бұрын
Haha Thanks Archana !! I love his accent tho 😂😂😂😂I mean who doesn't right? 😅
@aanchalsharma52644 жыл бұрын
@@TheAdityaVerma but you teach as a elder brother or a friend ...
@aanchalsharma52644 жыл бұрын
@@TheAdityaVerma thank u How to select which term to take as row and column.... What if we take vice versa???
@sasirekhamsvl95043 жыл бұрын
love your videos. If you did not made this playlist I might have never understood DP.
@aishwarya18953 жыл бұрын
Literally thanks a lot from the bottom of my heart
@nikitajaiswal91122 жыл бұрын
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
@Rajmayank242 жыл бұрын
In which language u code??
@rakeshrao2cool3 жыл бұрын
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
@AniketSinha2914 жыл бұрын
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] , ...)
@SourabhAnandJha3 жыл бұрын
sahi baat mere coder!!
@sahil10532 жыл бұрын
nobel prize laya jae bhai k liye😪😐😐
@es_amit9 ай бұрын
20:25 for changing max to OR, because if we found any subset of having sum == target then it means the main problem answer also is true so for making OR it will return true if we found any of the subset which having sum of target
@huntrz2 жыл бұрын
Aditya, I am not exagerating. You truly deserve the Dronacharya award had they been giving it for academics.
@nitinchaurasia89104 жыл бұрын
@Aditya Verma how to print all the subset after we create the matrix....... ??
@HarshitGupta0053 жыл бұрын
take a global list and fill that once you reach the answer
@karnatisaishashank12583 жыл бұрын
@@HarshitGupta005 how we can fill
@gauranshverma43644 жыл бұрын
You are doing a great job bhaiya....God bless you..
@fahadisrar21954 жыл бұрын
I am a GSOCian but my advanced CP isn't good enough...This is really helpful....Thanks a lot @Aditya Verma :)
@vaibhavgupta57764 жыл бұрын
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
@ankitkumaryadav5623 жыл бұрын
One of the Best tuturial>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
@sayleeshenoy50494 жыл бұрын
I saw many dp videos, so far this one is the best. Thanks for such great explanation. Keep posting such videos!
@sudhanshusharma91234 жыл бұрын
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.
@NishantSethigeek2 жыл бұрын
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)
@sudhanshusharma91232 жыл бұрын
@@NishantSethigeek 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.
@sanghamitrahota11624 жыл бұрын
This was a really nice explanation. I was stuck in this from a day , couldnt relate. Thanks 😁 please keep making videos
@TheAdityaVerma4 жыл бұрын
Thanks !! I am glad it helped you !! Do share and subscribe.
@factoworld9527 Жыл бұрын
@@TheAdityaVerma bhai aap legend ho please video banao aur
@NehaGupta-zc3mo3 жыл бұрын
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.
@sahil10532 жыл бұрын
they don't like to understand things
@SohamDutta22210 ай бұрын
thank you for making this excellent video!! We all are grateful to you! Soon I will get a good job. Thanks to you!!
@DeepakSingh-sy4ws4 жыл бұрын
u r best bro.. i have learnt from many youtubers but you and traversay media are best .. ur basic is clear..
@gurpartapsingh16934 жыл бұрын
It would be really nice if you can dry one problem at the end of the video. Keep the good work going!
@sarthakagarwal2213 жыл бұрын
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 ?
@MALIWAL10003 жыл бұрын
Yes he has patreon now, check new videos for link.
@sarthakagarwal2213 жыл бұрын
@@MALIWAL1000 yes, already a member
@GauravKumar-lb6ze3 жыл бұрын
have you got TLE with memoization?
@tanvivarshney60333 жыл бұрын
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🤗
@ak673734 жыл бұрын
Bro please make videos on tree also ...🙏🏻🙏🏻it will be helpful for my interview....make all videos on trees
@testertest85712 жыл бұрын
Completed 7 out 49 video....I will comment upto lecture 35 ., today on every video for sure..
@vaibhavm10074 жыл бұрын
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?
@kirtikhohal33132 жыл бұрын
Yes , i wrote the recursive function first , and then memoized it, and then I went on to write the actual iterative code
yes, I agree with this. Starting from a recursive solution seems more understandable and good in an interview.
@noobcoder80422 жыл бұрын
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.
@ayushsingh38773 жыл бұрын
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.
@utsavsharma4542 Жыл бұрын
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
@nitwaalebhaiya3 жыл бұрын
Sir your way of teaching is just great. I don't have words to thank you🙏🏻🙏🏻🙏🏻🙏🏻
@kirtikhohal33132 жыл бұрын
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??
@kirtikhohal33132 жыл бұрын
@@KazHachiOreki Sorry, but your explanation doesn't answer my question.
@namashsharma7550 Жыл бұрын
should i try to solve tabulation problems using recursion + memoization to better understand dp?? suggestions??
@navaugustt2 жыл бұрын
Best explanation watched on fractional knapsack based problem solving using DP 🤩🙌❤️
@praffuljavare16514 жыл бұрын
Great job correlating this problem with the knapsack problem! However I think you did not explain accurately, what t[i][j] = t[i-1][j-arr[i-1]] || t[i-1][j] actually means. From what I understand, the statement means that if the first i-1 elements are able to make the sum j, then great, else check whether it is possible to make the sum of j-arr[i-1] using the first i-1 elements. Please correct me if I am wrong.
@abhisheksuryavanshi96754 жыл бұрын
please refer previous video on 0/1 knapsack
@priyarathore92663 жыл бұрын
Best DP course on internet!
@aseembaranwal4 жыл бұрын
You applied divide and conquer in making columns on Paper. CSEian rock!!
@rajvijen4 жыл бұрын
Yo Bro, I thought same 🙂
@abhijitmukherjee17054 жыл бұрын
I think the DP code that you have written for subset set part, in that there should be a slight variation. in the part where you have compared the two boolean value, at that position t[ i ][ j - arr [ i - 1 ]] will be t[ i - 1 ][ j - arr [ i - 1 ]], have a look or correct me if I'm wrong.
@adityadutta9854 жыл бұрын
There's a pinned comment for this typo. Look at the pinned comment. It's just a typo
@paraslaul33074 жыл бұрын
codeforces.com/problemset/problem/1113/A can you solve this problem of dp?
@SumitVerma-ln5nz3 жыл бұрын
@@paraslaul3307 #include #include #define int long long int #define fio ios_base::sync_with_stdio(false);cin.tie(NULL); using namespace std; int dp[101][101]; int minFuelMoney(int n, int v) { for(int i = 3; i > n >> v; cout
@AltafHussain-on2oe4 жыл бұрын
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
@knandan63794 жыл бұрын
mazaa aagaya bhaiya... aag laga diye.... iit-jee k coaching k din yaad aagaye.
@karoseha5521 Жыл бұрын
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!
@MOHITPATIDARRA3 жыл бұрын
Thanks sir ,because of these video, grasping concepts of Dp become easy.
@softwaredevelopment43924 жыл бұрын
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 KZbinrs (waste of time + energy) . When are you going to complete this playlist of DP. ?
@ShivamKumar-cv7jv4 жыл бұрын
i think for this question recursion is more efficent, we just return where we find true and not recurse further.
@jaychotalia75423 жыл бұрын
@Aditya Verma , Sir as you said there are two ways of identifying DP question, 1) Choice 2) Optimal. But int this question they are not asking for any max or min value. Then how to know this can be solved via DP also ?
@Shourya_performs2 жыл бұрын
Actually the main question is minimize the length of the subset to get a desired sum. For example- arr[ ] : [2,3,4,5,10] sum : 9 possible subsets are : [2,3,4] and [4,5] but output should be of minimum length of subset so [4,5]. This is just a easier version of that problem.
@amitshah8173 жыл бұрын
Garda uda diye bhaiya🔥🔥
@022_cse-csdeepakkumarsain711 ай бұрын
Fabulous aditya bhaiya Great
@anushkabansal31763 жыл бұрын
Why did we wrote the Top-Down method? We should usually write Memoisation method right?As explained in previous videos.
@rishabhmalhotra22253 жыл бұрын
Sir please add recursive + memoization approach for this and subsequent problems🙏🙏🙏🙏
@ankurbanerji66056 ай бұрын
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.
@curiossoul3 жыл бұрын
So good. Could you please add a video on printing the subset. There are solns over different sites but would like one here
@kireeti11202 жыл бұрын
the similarities are explained greatly brother, thanks for your effort🙏
@tusharsingh24394 жыл бұрын
Great videos ! I had a doubt, in lecture 1 it was told that dp problems can be identified if they have two characteristics : 1) Choice 2) Optimial requirement(max,min,etc) in this problem what are we optimizing ? (in knapsack we were maximizing profit)
@TheAdityaVerma4 жыл бұрын
We have choices here !! For each element we have a choice whether we want to include it or not in our subset!!
@tusharsingh24394 жыл бұрын
Aditya Verma Thanky bhaiya, so all in all it should have either of the two characteristics?
@ankitdubey93103 жыл бұрын
@@tusharsingh2439 yes
@hiteshkaushik14682 жыл бұрын
@@tusharsingh2439 no "either of two" is a wrong understanding. A lot of optimization problems can be solved using greedy also. "Choice" and "Optimization" are rough identification markers that can be used to solve medium level DP problems. Many a times, these choice and optimizations markers are not visible directly in the problem statement. Another identification marker is this: If you try to come up with a bruteforce solution, you will need to evaluate all possible subsets of the given array. If array size = n, then total subsets = 2^n and this number is exponential. Trying out so many possibilities will obviously lead to a "Time limit exceeded" verdict and hence DP can be tried in such problems.
@himanshugupta45543 жыл бұрын
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
@shwetanknaveen3 жыл бұрын
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
@PankajGupta-gh9cm3 жыл бұрын
if we write the memoization code for this problem then after the base condition how to return the value if this already calculated since we create a boolean matrix then for each cell we have only two values either or false then how do we know if the current cell value is already calculated or not
@hishailesh774 жыл бұрын
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
@baldevverma58353 жыл бұрын
table bhi optimised way me banai hai waah n/2. true coder
@RohitSharma-lz8db4 жыл бұрын
Great explanation. But How would we do the memoization of this problem?
Bhai, aap bole ki isko kaise print karwana hai (sahi wala pattern) wo bhi dikhayenge. Kya wo kisi aur video mein hai? Wo bhi DP se hoga kya? Edit: Kya humlog column wise upar jake jaha pe True---> False mein badal raha hai wo element leke, uska weight minus karke uske upar wale row mein weight minused position mein jaye aur fir column mein dekhe ki true kaha false mein change ho raha hai...aise trace karke elements dhund sakte hai kya? Just thought of it!
@Ayush-jz5um Жыл бұрын
20:09 why did we use OR operation........... can we use AND or something like that... please someone clear my doubt.
@AkashKumar-tb9jv Жыл бұрын
beacuase in AND both condition should be true for result as true. but in OR one true and one false result true.
@gamerhu74623 жыл бұрын
JUST A REQUEST NEVER STOP UPLOADING KCH BHI KOI BHI TOPIC CHLEGA !!!!!! the way u make us understand things are amazing!!!
@Akshitgupta14 жыл бұрын
Summary at the end was an awesome wrap up💯
@aminesouley82522 жыл бұрын
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