In my opinion LIS makes sense more with form 1 by keeping the previous index in state and decide/choose for the current index but ultimately both forms are giving same TC so both are good 😊
The optimal substructure in LIS is: for any element at index i, LIS starting with this particular element is going to be Max of all the LIS'es on its right hand side that start with an element larger than the element at index i, incremented by 1. If we find LIS starting with every element in the sequence, one of them ought to be the LIS of the entire string. Optimal substructure in 0/1 knapsack (form 1) is: The optimal solution to the problem is going to be a combination of elements of the input sequence whose elements sum up to
Present. Also i solved the last problem in 2 ways. One using the sorting the a[i][j] in decresing order.i keep a vector of pair of pair int int. I store the a[i][j] ,i,j. The sorted in decreasing order of a[i][j]. Then keep intialise dp to -1. Then chevk if it is -1 go for rec else move on. Then if the cell is not visited then go for recurrenec else dont go. And another one as you give hint that the dirty water is coming for upper three cells so the first cells will always be clean . Then we check the maxtime the dirty water will come down to this cell and check if the a[i][j] of the cell is greater than that time it will be clean.
In case of sun problems if we written -inf then in some cases it overflows and get convert to positive value and vice versa and we don’t want to use long then what should we do although in this question you are only making valid calls which helps in avoiding that return value but in some problems it’s hard to make only valid calls.
1. avoid using dp array for answer. In this LIS it works but might not work in other problems. 2. to check if dp state is visited earlier or not use another done[][] array because the return value could go beyond -1(more negative in second problem) for dp and might cause inconsistenty.
Yes you are right ,After performing all the rec calls , we can print the last element of dp array(dp[n-1] as our answer ,since it store the maximum LIS value .
I tried to solve the LIS problem using Form 1 itself but realised that while calling the function, i.e., lengthOfLIS(level = 0,lastTaken = 0), we can't really take the initial lastTaken as 0 since it means that we are starting from the first element and taking the first element as lastTaken itself. But the catch is that we can't even take -1 as the lastTaken for the initial call as it would try to access dp[0][-1]. So do we need to keep another visited bool array as you had suggested in case of the DP returning negatives. How to proceed on this one ? Or did I miss something completely ? Please help. int n; int arr[10001]; int dp[10001][10001]; int lengthOfLIS(int level, int lastTaken) { //base case if(level == n) return 0; //cache check if(dp[level][lastTaken] != -1) return dp[level][lastTaken]; //choice 1 : Not Take int ans = lengthOfLIS(level+1, lastTaken); //check if(arr[level] > arr[lastTaken]) //choice 2 : Take ans = max(ans,1+lengthOfLIS(level+1, level)); //save and return return dp[level][lastTaken] = ans; } int main() { cin>>n; f(i,n)cin>>arr[i]; memset(dp,-1,sizeof(dp)); cout
just cache it in dp[level][last_taken+1] :) Also add another condition if(last_taken==-1 || nums[level] > nums[last_taken]).. while picking since you need to explore the path even if u havent picked any element previously
Hey Vivek. I tried solving CSES "Coin Combination 2" for the whole day and I'm stuck on it. Like I'm not getting an idea to cache only distinct ordered coins. It will take only 5 mins to explain the approach. Please Please Please. Do explain, please. I am solving it with your approach only. Please do explain that problem in your taught approach. Thank you.
Vivek in Lis problem of form 2, in solve function { For() { Rec call; } } Rec call's Time complexity is n^2; That we are calling in for loop of n; So, is it over all time complexity is O(n^3)? Please clarify @vivekgupta3484
Vivek please do take sessions for every other concept(strings,greedy,tries,segment trees,tries) just like you took for dp
In my opinion LIS makes sense more with form 1 by keeping the previous index in state and decide/choose for the current index but ultimately both forms are giving same TC so both are good 😊
The optimal substructure in LIS is: for any element at index i, LIS starting with this particular element is going to be Max of all the LIS'es on its right hand side that start with an element larger than the element at index i, incremented by 1. If we find LIS starting with every element in the sequence, one of them ought to be the LIS of the entire string.
Optimal substructure in 0/1 knapsack (form 1) is: The optimal solution to the problem is going to be a combination of elements of the input sequence whose elements sum up to
🔥 thanks
for 2nd ques i thought this way but later i came to know. how stupid i'm
rec(r,c){
// base case
if(r
Nice Video Sir ji
best DP resource
If we see dp(some state) depends on prev state it can be form 2 or ending at this form.
great : )
Nice🔥
21:00
6:45 Shouldn't it be arr[L] < last?
because DP(L, last) is LIS from L to N
no here , the last represents the last element taken , so it should be last
@@mvssguptajagadesh3269 Yeah got it. Thanks!
I thought from L to N means we're moving from right to left 🙂
on 2nd question can we apply dijkstra algorithm...?
the max path sum question is some what like prefix sum
Present. Also i solved the last problem in 2 ways. One using the sorting the a[i][j] in decresing order.i keep a vector of pair of pair int int. I store the a[i][j] ,i,j. The sorted in decreasing order of a[i][j]. Then keep intialise dp to -1. Then chevk if it is -1 go for rec else move on. Then if the cell is not visited then go for recurrenec else dont go. And another one as you give hint that the dirty water is coming for upper three cells so the first cells will always be clean . Then we check the maxtime the dirty water will come down to this cell and check if the a[i][j] of the cell is greater than that time it will be clean.
In case of sun problems if we written -inf then in some cases it overflows and get convert to positive value and vice versa and we don’t want to use long then what should we do although in this question you are only making valid calls which helps in avoiding that return value but in some problems it’s hard to make only valid calls.
If you're doing this in Java, make sure to use long instead of int. Since the values are at most 10^7
if some one who is not good at dp i realy say you shoud continu this playlist
1. avoid using dp array for answer. In this LIS it works but might not work in other problems.
2. to check if dp state is visited earlier or not use another done[][] array because the return value could go beyond -1(more negative in second problem) for dp and might cause inconsistenty.
I feel both form 1 and form 2 are interchangeable at times.. Isn't it??
Correct.
yeah @Imran Hussain agree with you
why not use dp array in the for loop of solve() while finding the best
Yes you are right ,After performing all the rec calls , we can print the last element of dp array(dp[n-1] as our answer ,since it store the maximum LIS value .
@@mvssguptajagadesh3269 no like its not necessary that it would be n-1. We will have to iterate over the dp array to find
I discussed this in the Doubt stream yesterday... in this it will work... but refrain from direct usage of DP array.
@@sachitsankhe5102 yes , you are right . We have to iterate over the DP array to get the Max value.
@@mvssguptajagadesh3269 no some of states might not be computed as required call function only
can someone share the code for form 1pls
I tried to solve the LIS problem using Form 1 itself but realised that while calling the function, i.e., lengthOfLIS(level = 0,lastTaken = 0), we can't really take the initial lastTaken as 0 since it means that we are starting from the first element and taking the first element as lastTaken itself. But the catch is that we can't even take -1 as the lastTaken for the initial call as it would try to access dp[0][-1]. So do we need to keep another visited bool array as you had suggested in case of the DP returning negatives.
How to proceed on this one ? Or did I miss something completely ? Please help.
int n;
int arr[10001];
int dp[10001][10001];
int lengthOfLIS(int level, int lastTaken) {
//base case
if(level == n) return 0;
//cache check
if(dp[level][lastTaken] != -1) return dp[level][lastTaken];
//choice 1 : Not Take
int ans = lengthOfLIS(level+1, lastTaken);
//check
if(arr[level] > arr[lastTaken])
//choice 2 : Take
ans = max(ans,1+lengthOfLIS(level+1, level));
//save and return
return dp[level][lastTaken] = ans;
}
int main() {
cin>>n;
f(i,n)cin>>arr[i];
memset(dp,-1,sizeof(dp));
cout
That's a very good issue... we will learn this in a session today.
just cache it in dp[level][last_taken+1] :)
Also add another condition if(last_taken==-1 || nums[level] > nums[last_taken]).. while picking since you need to explore the path even if u havent picked any element previously
Or you can save the items dp[leve] [ lastTaken+1] 1 based indexing for dp arraay
Hey Vivek. I tried solving CSES "Coin Combination 2" for the whole day and I'm stuck on it. Like I'm not getting an idea to cache only distinct ordered coins.
It will take only 5 mins to explain the approach.
Please Please Please. Do explain, please.
I am solving it with your approach only. Please do explain that problem in your taught approach.
Thank you.
Vivek in Lis problem of form 2, in solve function {
For() {
Rec call;
}
}
Rec call's Time complexity is n^2;
That we are calling in for loop of n;
So, is it over all time complexity is O(n^3)?
Please clarify @vivekgupta3484
DP use kia hai na bhai,toh amortized TC o(n^2) hi hai; Per state:max transition possible n hai(due to loop),islie TC: num(states)*(num transitions+1)