DP 18. Count Partitions With Given Difference | Dp on Subsequences
Вставка
- Опубліковано 1 сер 2024
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3r8mG5b
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the problem of count partitions with given difference. This problem is the fifth problem on DP on Subsequences Pattern. Please watch DP 17 before watching this.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
![Lp. Последняя Реальность #107 РОДНОЙ ДОМ [Финал] • Майнкрафт](http://i.ytimg.com/vi/IK3QKzKUlHM/mqdefault.jpg)
I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you.
Keeping a like target of 500 ❤✌🏼
understood
Understood
I'll be honest, I was bamboozled with the 0's in array edge case since DP17 and I was simply unable to find a clear answer from the comments. Had I simply closed my eyes and went ahead with DP 18, I would have legit saved ~ 2 hours of confusion!!
Thankyou so much Striver, this lecture cleared all my doubts 🔥🔥🔥🔥🔥
Those confusion and doubts and 2 hours will only help in longer run. Good work on not directly jumping to another video without clearing your doubts on your own.
for real should have moved on to this video those comments were so confusing
Samee
sameeeeeeeeeeee
I studied DP from aditya verma, but was never able to figure out how to handle the zeros in the array, you made it super easy, Thanks!
but aditya verma always tell you the in=dentification and where u can use this apparoach nd similar questions he is the god of cp ik he skip the case of 0 in array but aditya verma is for cp where u can use which approach and how to identify which approach by seeing solution
@@entertainmenthub373 God of cp is tourist.
its not like he was not able to figure out , he always gives an intution to solve the problem , not like come and tells you the whole solution.
hats off man,, spent 2 hours on DP17 to fix that but after watching this DP 18 everything went super smooth
Understood! Hats off to ur dedication, u are still teaching while suffering from fever.
The deduction of (totalSum - D) / 2 was amazing. Understood!
Striver's concept explanation is so cool, easy and easily get stuck into the head. I wish to meet him one day and say a lot of thanks to him.
understood until 14:00 ❤ .
Will learn the optimization later
Hello,
The tabulation code is not passing all test cases in both videos dp-17 && dp-18. Is anyone facing the same problem. Pls HELP.
Understood 💯💯Great Explanation. Thank you very much for all you efforts🔥🔥
Us, but the way you transformed the problem into previously solved problem is amazing , that's the way we have to think ... Thanks ❤
understood. Also thanks for explaining Space Optimization so good. I am from tier-3 mechanical never knew all these stuff
UNDERSTOOD.........Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
I was confused with the previous video 0 case, but now understood. Thanks.
To deal with the 0 case, we can also take the dp array to be of size [n+1][sum+1] and initialize the dp[n][0]=1
int[][] dp = new int[n+1][sum+1];
dp[n][0]=1;
for(int index=n-1;index>=0;index--)
Another modified target could be (difference + totalSum)/2;
To explain this how this came is :
s1= sum of elements in subset 1
s2 = sum of elements in subset 2
s1 - s2 = d (We need to find 2 subsets with difference d )
s1 + s2 = totalSum (We know the sum of 2 subsets would be equal to the total sum of array)
Adding these 2 equations , we get s1 = (d + totalSum)/2, thus we only need to find a subset with sum s1.
But this will increase the space req :)
@@takeUforward Oh Okay , I didn't think about that !
@@chetanthakral5322 lol, I thought the same thing, but its not pure math its cs.
@@varunaggarwal7126 how this increases the space.. can u explain
@@UCSParnashreeDas it's been 1 month,lol i have to revise this dp, but I guess you can see + sign while striver is subtraction, means less
Understood 👍. Hats off to your dedication for us. ♥
UNDERSTOOODD!!!
Thank you, Striver!!
Great Explanation Striver , Thanks
After this video, they updated the problem! Real influencer
Already understood before starting of video that's what Striver teaches us
understood. Thank you so much
understood , the space optimization is amazing sir
solved this problem on my own very proud of this
Understood! Striver. The best Software Engineer himself
Understood Bhaiya!
we can also use :
if(ind < 0){
if(sum==0) return 1;
return 0;
}
apart from these conditions:
if(ind == 0) {
if(sum==0 || num==arr[0]) return 1;
if(sum==0 && arr[0]==0) return 2;
return 0;
}
this makes the code really simple to understand. perfect base case.
Best Bhai
@@anuragprasad6116
but how will you handel -1 index in tabulation?
Understood. Thankyou sir.
bro doing gods work
"UNDERSTOOD BHAIYA!!"
UNDERSTOOD... !
Thanks striver for the video... :)
4:48 or I think, we can go 1 step deeer into indx = -1
then base case would be simpler
if (indx == -1) {
if (sum == 0) return 1;
else return 0;
}
Then how do you take care of base case in Tabulation. As dp array cannot have -ve indexes.
@@introvert9112k for that i think we would need to make 1 indexed arrays of size n+1 having an extra 0 index free
Understood! Thank you so so so much!!!
You have literally made dp look so easy !
Thank you striver ! Just a note : writing recursion from 0 to n-1 looks far easier to handle bases cases than writing recursion from n-1 to 0 on subsequence problems
but for me it creates problem while writing the tabulation form. Esp. with all the subsequences questions.
yeah man, we have to start from n-2 if we do 0 to n-1 in recursion@@santoshpokhrel7693
yaa bro really it creates confusion in tabulation
@@santoshpokhrel7693
Thank you so much!
Understood
Thanks Striver for this Dp series
In the space optimized solution why the loop sum=1 to target doesn't work as we have been doing previously and setting curr[0] =1 since for any index with target as 0 there is only single subset. Can someone explain please?
Understood, well explained.
ok
hey can anyone please clear my doubt. I'm applying DP-16 concept.like after filling the tabulation with boolean, check and try for every s1, that it's possible to get standing on last index, if possible then calculate s2 and check the condition given in the qsn and increment count, Now this method is not working, I think it's because the tabulation is not recording duolicacy, e.g, In array if the sum 7 is made by more than one way, then it's not taking that record, and while checking for (s1>s2 && s1-s2==d), only once the count is increasing,
is it the actual reason of failing ?
Understood, sir. Thank you very much.
Understood 💯💯Great Explanation
For Those who did not understand why total sum-d has to be even so imagine totalsum=15 and d=2 now count s2=(15-2)/2 it will give s2=6; ans s1-s2=d so s1=2+6=8 now here it is said that s1+s2=totalsum but s1+s2=14 which is not equal to total sum to total sum-d has to be even
thankyou my guy🙌
In Lecture 17 , we can sort the vector and reverse it, then no need to change base case it will work absolutely fine.
Yes, but it will take extra time complexity
@@riddhibandyopadhyay584 ya you're right but can be done ✅ with this approach .👍
Nicely Explained! Understood!
Understood Sir.
That algebra at 10:15 is crazy I would never see that under the time constraints of a real interview. It's brilliant tho
I thing the simplest way to get rid of so many conditions of 0's we can simply start the recursion for 0 to n-1; then we will get correct ans i.e.4;
Yes, and it would also work even if the array doesn't contains any zeroes.. The base cases are also so simple to handle over here.
completed subsequences set problems great learning
Understood ❤
Thank you so much I've understood
If we have handled the case num[0] == 0 previously then why we are checking it again for num[0]
For Problem 17 , I struggled a bit in Tabulation while writing the base cases for the new changes.
All 3 cases covered, also notice the bases cases are written in reverse order, so that the priority is given to the last one if its true.
One more thing since we are considering the case for i = 0, please start the 2nd loop of target from 0 till k(inclusive). Happy learning!
dp[0][0] = 1
if arr[0]
Hey, thank you. Great comment.
another base case(Better and Concised):
if(ind
Thankyou very much for explaining base case of last question. I was stacked for last 6 hours. ❤️❤️
Hey, Striver I understood the logic in this but how are you able to think of using logic like this very quickly ? , i didn't get that by looking at the question.
*********** Iterative Code for the count number subsequence whose sum is k ( & 0
int gfg the case where 0 can be in the begining can be solved by sorting given array in decreasing order but this will increase time compl,but will still pass test cases;
Understood 🔥🔥
Understood!
at 15:53 , the target should run from 1 to sum right? we have run from 1 to sum in the count subsequences with sum k also, why did you take from 0 to sum?
Thank you striver, made it super easy and interesting to learn DP. "UNDERSTOOD" 💓💓
just mind blowing how you came up with the modified target, kyse kar lete ho bhaiya?
what we do in case of negative elements if its given?
understood!
Superb Bhaiya
guys watch at 10:10
Amazing Concept
Again and again Thankyou bhaiya Aka Striver
Thank you
What if we find with target = totalsum
Then at n-1 iteration of tabulation find S1 and S2 by totalsum - S1.
Then If S1>=S2 and S1-S2=D we can return True else False
UNDERSTOOD
Understood🎉
OMG bhaiya ...simple "genius"
loved it
Instead of changing the code we can just add a if statement before "take" variable that if arr[index]== 0 then skip it...
us
But i got confused as in DP 18 ques , it is written that two partitions have their union as Whole array . It should have been given that both are exclusive of each other , for being self-explanatory well.
You have expressed S1 in terms of S2 then solved this problem. Can we do vice versa then solve this problem?
for DP 17
for [ 7,1,0,2,5] with tar=7
Method 1: originalAns*(pow(2,n))
Method2: Changes in base case will that work? I can see from recursion tree there would be redundant calls at level where 0 is considered
How do I write the base case in tabulation, Could you please tell me?
Method 1 is time intensive if let's say the no of zeroes were 15-20 in an array...Hence method 2 with handling zero in the base cases is required at such cases.
Calculating Max Sum of Array with the following condition, If A[i] element contributing in max sum,than you can't consider A[i]-1 and A[i]+1 element for max sum contribution, if present in array .
Note: Elements of the array can be repeated multiple times. It's unsorted. It can have 1 to n number of element.
eg:
int A[ ]={1,6,7,1,2,3,3,4,5,5,5,6,9,10};
If I consider 10 as contributing max sum, I can consider 9 and 11. (Here 11 is not present but 9 is present still we can’t consider it).
If I consider 5 (total max sum contribution 5*3) but can’t consider 4 and 6.
I have tried sorting and storing index and count in the ordered map. Also try to compare with unbounded knapsack criteria.
Still, I was struggling with an optimal and clear idea to calculate. Any idea how to approach it .
Create an array dp of size n, where n is the length of the input array A. Initialize all elements of dp to 0.
Sort the input array A in ascending order to simplify the comparison process.
Iterate through each element A[i] in the sorted array A.
For each element A[i], update the maximum sum at index i in the dp array based on the following condition:
If A[i] is the first occurrence in the sorted array or A[i-1] and A[i+1] are not present in the sorted array, then set dp[i] to dp[i-1] + A[i].
Otherwise, set dp[i] to the maximum value between dp[i-1] (excluding A[i]) and dp[i-2] + A[i] (including A[i]).
After iterating through all elements in the sorted array, the maximum sum will be the maximum value in the dp array.
Can anyone please explain why target is starting from 0 here? in all other problems it's starting from 1. If I take 1, some test cases are failing
15:00 the most important point to be noted if you are in an intervie
bhaiya in count subset problem which u had taken earlier , in tabulation the loop started from 0 to sum but when sum==0 it has been handled previously right? then it should start from 1 right? as in problem subset sum==k u started the sum loop from 1 to sum as for sum==0 we have handled it previously before the loop.
Yes u can, won’t be an issue :)
@@takeUforward yes i did that in the count subsets problem, but when I did that in the current problem of partition i.e. looping from 1 to sum it's giving WA, but when i changed to 0 to sum it's giving correct and. Why so?
@@aryanagrawal4794 because in partition at 0 there are other cases to handle. Here at 0, its take and notTake, hence
@@takeUforward ok bhaiya got it.
@@aryanagrawal4794 Hey can you explain it to me?
please tell us the time when this amazing course will get end......expected time??
March
just add this in previous question:
```
if (i < 0)
{
return !target;
}
```
Understood !!
why return 0 case is not considered in base case of tabulation?
understood
actually we can make the base case as
if(index == -1) {
if(tar == 0) return 1;
return 0;
}
underrated! taking this as a base case really simplifies the solution.
In that case my recursive code was going from 0 to n-1 and to avoid case of zero I sorted my array hence all the zero cases were sorted
you don' t even need this , just go from 0 -> n , and if at n , target == 0, return 1 else 0 , all other cases are already been taken care off , if you do in this way .
How ?
our code will do this will we are making the recursive calls at n-1
understoooooooood
understood😃
amazing
Understood.
Hare Krishna..!! understood.
In lecture 17, can we handle the cases having zeroes by just multiplying our previous answer with pow(2,n) where n is the no. of zeroes
I discussed that only, but that adds a log n
@@takeUforward Does 1ll
Can anyone explain why are we always initializing the DP[0][i] with val[0]:
for(int i = weight[0];i
Understood. Best on whole yt.
as we are handing separately so now we need our TARGET LOOP should start from 0...correct ??
if someone is going from 0 to n
if(i==arr.length)
{
if(tar==0) return 1;
else return 0;
}
this will handle the case for zero (1, 0,0 ) will give -> 4 (if tar = 1)
Wouldn't it be better to have one more recurssive call and check if ind == -1 then check if target==0 return1 else 0 it would remove the return 2 and other if condiditons althought we are having 2 more recurssive calls but still it makes the code look cleaner and similarly in tabulation we can iterate over j loop from 0
If we had added the equations then s=T+D/2 would've happened which would remove requirements of ec 1
Understood!!Thank you