This time I was able to solve this problem on my own before watching the video and got accepted. Thank you Striver for your entire DP playlist without your playlist I couldn't solve any DP problems.
Hey Striver you have developed my thought process to a far extent..... I was able to space optimise this question to just 1 cur 2D vector without even using prev..... This is possible only because of you. I tried to think what does it require to fill a cell and then realized that using only cur would also work.... Thanks a lot.....you are my motivation
Understood, I wasn't not consistent from past 1 week, but still trying to practice daily on DP at least. Thank you for this Holy Playlist for DSA learners out there.
Striverrrrrrrr i cant thank you enoughhh, i never thought i would ever be able to solve a hard ques by myself and that too of dp :) but I did this on my own a big big bigggggg thank you and shout out to you :) thanku soooo much❤❤you are a magician❤
Bhaiya before folowing this series I just start by tabulation in dp problems and ends up doing nothing , but you have taught so beautifully that now when I see a new question, first I try to do it by recusion and then convert it to memoization or tabulation. Thanks Bhaiya for this amazing series.
Did this question upto the space optimization part all by myself without seeing the video. Thank you striver for such quality content in your dp series.
I have intentionally given very much time to DP 36: to buy and sell stocks unlimited time and it helped. I have done all the remaining question without seeing the solution videos. Thanks STRIVER. UNDERSTOOOOOOOD😃
Thanks Striver so much. I was able to do recursion and memoization earlier, but i could just never relate it to tabulation and never ever did space optimization. Today I am confident if I have done recursion, I can go all way till optimizations.
I watched all dp videos before this one and was able to solve this question on my own without watching the video. thank you so much striver...your teaching is really tremendous.
Thank you so so much Striver. I did the recursion, memoisation, tabulation and space optimisation approach on my own. The n*4 dp array approach is really good. UNDERSTOOD :)
i can defintely say that i would die with out learning DP , if i didnt met striver, for every problem , he is keeping every possible solution,thats a great way though, thank you for providing this playlist , u are a way providing a new life for many people ,who are watching this , my all love for you boiiii
Awesome bro , dp ke series dekh ke , ab pehla task recusive solution likhna rehta hai, uske baad toh fir memoisation, tabulation , space optimisation ab easily ban raha hai . DP is not that tough, which i was expecting, even today i learned 3D dp, before i was thinking aree yeh sab kya hai 3d ,4d dp,kitna hard hoga. Thanks ❤❤
in tabulation, first base case can be skipped as we are already initializing the vector with zeroes. we can skip second as well but with a slight change that we can run the inner loop from cap = 2 to cap > 0 instead of cap >= 0 because we know that when cap is 0, the profit is 0 so do not disturb that value.
Another way to frame this question. Given an array, Find the max value of a - b + c - d such at index of a is less than index of b, index of b is less than index of c and index of c is less than index of d.
Thanks striver you are the best teacher of DSA in the world, i am definately sure that even professor at harvard or mIT can't explain like u... UNDERSTOOD
Bro you can also optimize this to Single Array, here is the code int maxProfit(vector &prices) { int n = prices.size(); vector dp(5, 0); // base case // just initialize the linear dp with 0 for (int index = n - 1; index >= 0; index--) { for (int transaction = 3; transaction >= 0; transaction--) { int profit; if (transaction % 2 == 0) { int buying = -prices[index] + dp[transaction + 1]; int not_buying = 0 + dp[transaction]; profit = max(buying, not_buying); } else { int selling = prices[index] + dp[transaction + 1]; int not_selling = dp[transaction]; profit = max(selling, not_selling); } dp[transaction] = profit; } // dp = temp; } return dp[0]; }
For Java, Developers, I think this is easy way public static void main(String[] args) { int arr [] = {3,3,5,0,0,3,1,4}; int max = Integer.MIN_VALUE; int max1= Integer.MIN_VALUE; int temp =0; for(int i=0;ii) { temp = arr[i+1]-arr[i]; if(max
I was able to come up with the solution and coded it before watching the video but the test cases was not passing. Silly me, I assumed the second parameter given is the number of transaction to be made. So, I was passing `n` instead of `2`. After watching the video, I realised this mistake :P Thanks Striver for the amazing content, so far I am understanding and practising alot.
**** ALL CODES OF THIS VIDEO BELOW INCLUDING LAST PART OF Nx4 DP with space optimisation **** #include using namespace std; //Memoization int f(int idx, bool buy, int cap, vector &prices, int &n, vector &dp){
//Base Cases if(idx == n || cap == 0)return 0; if(dp[idx][buy][cap] != -1)return dp[idx][buy][cap];
4 Solution mentioned (Memoized CODE , Tabulation code , Space Optimized with 2 Array ,Space Optimized with 1 D array ) I ❤ you Striver. Memoized CODE :- class Solution { public:
int recur(int i,int trans,vector & nums,int n, vector& dp) { if(i == n || trans == 4)return 0;
Understood everything. Here is the space-optimized code you asked for: class Solution { public: int maxProfit(vector& prices) { int n = prices.size(); int cap = 2; bool buy = true; vector t(n+1, vector(5, 0)); vector prev(5, 0), cur(5, 0);
Hey Striver I have solved it using the concept that you taught at the last but I have solved for maximum k transactions instead of two. And I have space optimized it to a single 1D vector of size 2*k+1 Here is the space optimized code :- int maximumProfit(vector &prices, int n, int k) { vector cur(2*k+1,0); for(int transaction=0;transaction=0;index--) { for(int transaction=0;transaction
Solution for the other way: Memoization: class Solution: def maxProfit(self, prices: List[int]) -> int: def f(ind,arr,trans): if ind==len(arr) or trans==4: return 0 if dp[ind][trans]!=-1: return dp[ind][trans] if trans%2==0: profit=max(-arr[ind]+f(ind+1,arr,trans+1),f(ind+1,arr,trans)) else: profit=max(arr[ind]+f(ind+1,arr,trans+1),f(ind+1,arr,trans)) dp[ind][trans]=profit return profit dp=[[-1 for i in range(4)]for j in range(len(prices))] return f(0,prices,0) Tabulation: class Solution: def maxProfit(self, n : int, price : List[int]) -> int: # code here dp=[[0 for i in range(4+1)]for j in range(n+1)] for ind in range(n-1,-1,-1): for trans in range(3,-1,-1): if trans%2==0: dp[ind][trans]=max(-price[ind]+dp[ind+1][trans+1],dp[ind+1][trans]) else: dp[ind][trans]=max(price[ind]+dp[ind+1][trans+1],dp[ind+1][trans]) return dp[0][0] Space Optimization: class Solution: def maxProfit(self, n : int, price : List[int]) -> int: prev=[0]*(5) for ind in range(n-1,-1,-1): curr=[0]*(5) for trans in range(3,-1,-1): if trans%2==0: curr[trans]=max(-price[ind]+prev[trans+1],prev[trans]) else: curr[trans]=max(price[ind]+prev[trans+1],prev[trans]) prev=curr return prev[0]
} } //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Space optimization: class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int dp[][] = new int[2][3];
for(int ind = n-1 ; ind >= 0 ; ind--){
int curr[][] = new int[2][3];
for(int buy = 0 ; buy < 2 ; buy++){ for(int cap = 1 ; cap < 3 ; cap++){
I have gone through this problem using the way Tushar roy has thought now that is good no doubt but the way striver has done it I really don't need to remember anything.
You can also optimize this to Single Array int maxProfit(vector &prices) { int n = prices.size(); vector dp(5, 0), temp(5, 0); // base case // just initialize the linear dp with 0 for (int index = n - 1; index >= 0; index--) { for (int transaction = 3; transaction >= 0; transaction--) { int profit; if (transaction % 2 == 0) { int buying = -prices[index] + dp[transaction + 1]; int not_buying = 0 + dp[transaction]; profit = max(buying, not_buying); } else { int selling = prices[index] + dp[transaction + 1]; int not_selling = dp[transaction]; profit = max(selling, not_selling); } dp[transaction] = profit; } // dp = temp; } return dp[0]; }
@striver bhai yeh same memoization approach Sahil Srivastav ne apne bootcamp me samjhaya tha.. I'm just curious, did you guys had a common teacher who taught approach to you guys or you both have same thought process? 🤔 Ps- First viewer!
@@takeUforward, simple DP 😱😱😱, bhai ek time tha ki DP se darte the.. abhi tumhara, Sahil Srivastav, Aditya Verma ke wajah se lagta hai hum bhi DP kar lenge! Yep only recursion, memoization approach was explained in Sahil's bootcamp. Space optimization is your trademark! PS- Have some sleep bro.. Mental health is important too, can cause problems in older age if not taken care.. I understand mental tiredness caused due to ofc work + after ofc hours study(content creation in your case)
Hi Stiver.. amazing explanation.. One doubt : Top-down ----------------- you usually go from n-1 to 0 in "Top-Down" but here you are starting from 0 Bottom-Up ----------------- you usually go from 0 -> n-1 and go incrementally and last cell is answer On stock series this seems quite opposite to me.
"Top-Down" does not mean that you will always go from n-1 to 0. You can also go from 0 to n-1. It all depends on you how you want to solve the question.
10:41. i always knew he was a man of culture.
my man proved it again at 12:39
butt butt
I thought i was the only one noticing this since the start of this dp series, poor striver doesnt even realize😂😂
Code for the last part------
Memoization-
int f(int ind,int ts,int n,vector&prices,vector&dp)
{
//base cases
if(ind == n || ts ==4) return 0;
if(dp[ind][ts] !=-1) return dp[ind][ts];
if(ts%2==0)
{
return dp[ind][ts] = max(-prices[ind]+f(ind+1,ts+1,n,prices,dp),f(ind+1,ts,n,prices,dp));
}
else
{
return dp[ind][ts] = max(prices[ind]+f(ind+1,ts+1,n,prices,dp),f(ind+1,ts,n,prices,dp));
}
}
int maxProfit(vector& prices, int n)
{
// Write your code here.
vectordp(n,vector(4,-1));
return f(0,0,n,prices,dp);
}
--------------------------------------------------------------------------------------------
Tabulation-----
int maxProfit(vector& prices, int n)
{
// Write your code here.
vectordp(n+1,vector(5,-1));
for(int i=0;i=0;ts--)
{
if(ts%2==0)
{
dp[ind][ts] = max(-prices[ind]+dp[ind+1][ts+1],dp[ind+1][ts]);
}
else
{
dp[ind][ts] = max(prices[ind]+dp[ind+1][ts+1],dp[ind+1][ts]);
}
}
}
return dp[0][0];
}
---------------------------------------------------------------------------------------------------------
1-D Space Optimisation-------
int maxProfit(vector& prices, int n)
{
// Write your code here.
vectorahead(5,-1),cur(5,-1);
for(int i=0;i=0;ind--)
{
for(int ts = 3;ts>=0;ts--)
{
if(ts%2==0)
{
cur[ts] = max(-prices[ind]+ahead[ts+1],ahead[ts]);
}
else
{
cur[ts] = max(prices[ind]+ahead[ts+1],ahead[ts]);
}
}
ahead = cur;
}
return ahead[0];
}
Thank you Striver Bhaiya for this wonderful series.
Why can't we traverse transaction from 0 to 3???rather than from 3 to 0 in dp solution??
@@adityamane9312 we can traverse for(int t=0;t
@@tanyanema5102 but i gives wrong answer dude...
@@adityamane9312 It works for 0->3 as well
Wouldn't it be N X 5 then for Tabulation and Space Optimization ?
This time I was able to solve this problem on my own before watching the video and got accepted. Thank you Striver for your entire DP playlist without your playlist I couldn't solve any DP problems.
Recursion is magic ❤
and Striver is the magician 😂
@@rahulraj94391 🤣🤣
The only magician who teaches magic
Hey Striver you have developed my thought process to a far extent.....
I was able to space optimise this question to just 1 cur 2D vector without even using prev.....
This is possible only because of you. I tried to think what does it require to fill a cell and then realized that using only cur would also work....
Thanks a lot.....you are my motivation
4 trike to bta hi diye , 1 aur bta dena tha 5 complete ho jate......you are amazing striver.....thankuuuuu
This is the first time i solved Leetcode hard myself because of u Striver. Thank u so Much for this kind of teaching.
The Nx4 solution is amazing and very intuitive. Thanks a lot for explaining multiple solutions to the same problem!
Understood,
I wasn't not consistent from past 1 week, but still trying to practice daily on DP at least. Thank you for this Holy Playlist for DSA learners out there.
Welcome!
@@ScienceSeekho simp!
@@ScienceSeekho who tf are you?
Ooh what happened Paridhi why weren't you consistent??
simp
66.6% done ,
thanks striver broo to make me able to solve any of the dp pattern learn so far in this series.
Striverrrrrrrr i cant thank you enoughhh, i never thought i would ever be able to solve a hard ques by myself and that too of dp :) but I did this on my own a big big bigggggg thank you and shout out to you :) thanku soooo much❤❤you are a magician❤
Bhaiya before folowing this series I just start by tabulation in dp problems and ends up doing nothing , but you have taught so beautifully that now when I see a new question, first I try to do it by recusion and then convert it to memoization or tabulation. Thanks Bhaiya for this amazing series.
Did this question upto the space optimization part all by myself without seeing the video. Thank you striver for such quality content in your dp series.
I have intentionally given very much time to DP 36: to buy and sell stocks unlimited time and it helped. I have done all the remaining question without seeing the solution videos. Thanks STRIVER.
UNDERSTOOOOOOOD😃
Thanks Striver so much. I was able to do recursion and memoization earlier, but i could just never relate it to tabulation and never ever did space optimization. Today I am confident if I have done recursion, I can go all way till optimizations.
watching this video finishes the stock pattern for me thanks a lot striver
i solved the entire problem on my own
from recursion -> memoization -> tabulation -> space optimization
thnk u striver
Thank you very much for providing DP tutorials .
pls bring Next Series on Segment trees , fenwick tree .
I watched all dp videos before this one and was able to solve this question on my own without watching the video. thank you so much striver...your teaching is really tremendous.
I wasn't able to solve, but got a feeling of using another parameter to count the number of transactions left.
UNDERSTOOD........Thank You So Much for this wonderful video......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
predicted for first time the solution even its hard problem , Thankyou so much for providing conceptual understanding Striver
Understood both ways dp[n][2][3] & dp[n][4] ❤
Thank you so so much Striver. I did the recursion, memoisation, tabulation and space optimisation approach on my own. The n*4 dp array approach is really good. UNDERSTOOD :)
bhai bahut tagda samjhate ho yaar
all clear
i can defintely say that i would die with out learning DP , if i didnt met striver, for every problem , he is keeping every possible solution,thats a great way though, thank you for providing this playlist , u are a way providing a new life for many people ,who are watching this , my all love for you boiiii
I was able to get to N x 4 solution by my own. I can't believe this. You are greatest teacher. Thank you so much ❤
Awesome bro , dp ke series dekh ke , ab pehla task recusive solution likhna rehta hai, uske baad toh fir memoisation, tabulation , space optimisation ab easily ban raha hai .
DP is not that tough, which i was expecting, even today i learned 3D dp, before i was thinking aree yeh sab kya hai 3d ,4d dp,kitna hard hoga.
Thanks ❤❤
With your guidance , i am able to solve all types of buy and sell stock problems.
Understood!! Thank you so much bhaiya!!
"UNDERSTOOD BHAIYA!!"
Raj Vhaiya the technique using 4 variables is derived from Buy and Sell Stocks I.
Happy Guru Purnima coding Guru 🙇
in tabulation, first base case can be skipped as we are already initializing the vector with zeroes. we can skip second as well but with a slight change that we can run the inner loop from cap = 2 to cap > 0 instead of cap >= 0 because we know that when cap is 0, the profit is 0 so do not disturb that value.
no words for your contribution to all DSA learner :-))))
Thanks for the whole series, i have solved each and every problem till now and now i feel confident, will do cp a lot to gain speed and practice more.
Thank You Striver!!
You explained it so well, really a gem bro, I solved this one & next part of this myself without watching. Hats off to you!
Another way to frame this question.
Given an array, Find the max value of a - b + c - d such at index of a is less than index of b, index of b is less than index of c and index of c is less than index of d.
Thanks striver you are the best teacher of DSA in the world, i am definately sure that even professor at harvard or mIT can't explain like u... UNDERSTOOD
hi striver bhaiya i did this problem without even watching the video for a second using 3D dp. Thanks to u bhaiya
I hope you guys are doing extremely well
I solved this my self from recursion to tabulation. This is the best dp playlist
Understood! Thank you..
understood bhaiya .this is your one of the best series bhaiya. thank you bhaiya
Space optimized code for last approach -
int f( vector &prices , int n){
vector ahead(5,0) , curr(5,0);
for(int i = n-1 ; i>=0 ; i--){
for(int j = 0 ; j
Bro you can also optimize this to Single Array, here is the code
int maxProfit(vector &prices)
{
int n = prices.size();
vector dp(5, 0);
// base case
// just initialize the linear dp with 0
for (int index = n - 1; index >= 0; index--)
{
for (int transaction = 3; transaction >= 0; transaction--)
{
int profit;
if (transaction % 2 == 0)
{
int buying = -prices[index] + dp[transaction + 1];
int not_buying = 0 + dp[transaction];
profit = max(buying, not_buying);
}
else
{
int selling = prices[index] + dp[transaction + 1];
int not_selling = dp[transaction];
profit = max(selling, not_selling);
}
dp[transaction] = profit;
}
// dp = temp;
}
return dp[0];
}
For Java, Developers, I think this is easy way
public static void main(String[] args) {
int arr [] = {3,3,5,0,0,3,1,4};
int max = Integer.MIN_VALUE;
int max1= Integer.MIN_VALUE;
int temp =0;
for(int i=0;ii) {
temp = arr[i+1]-arr[i];
if(max
recursive dp is giving tle because in the dp declaration you have give size of 'n' rather it should be 'n+1'
bro, n is right,
recursive solution will always give tle, because of exponentioal tc
Awesome explanation both N*2*3 and N*4
space optimised
int n=prices.size();
vector before(5,0);
vector after(5,0);
for(int i=n-1;i>=0;i--){
for(int t=3;t>=0;t--){
if(t%2==0) after[t] = max( -prices[i] + before[t+1], before[t] );
else after[t] = max( prices[i] + before[t+1], before[t] );
}
before=after;
}
return after[0];
Very good explanation
hii striver thaanks i clearly understand dp for your playlist thanks bhai
Kudos to you man!!!!
I was able to come up with the solution and coded it before watching the video but the test cases was not passing.
Silly me, I assumed the second parameter given is the number of transaction to be made. So, I was passing `n` instead of `2`. After watching the video, I realised this mistake :P
Thanks Striver for the amazing content, so far I am understanding and practising alot.
**** ALL CODES OF THIS VIDEO BELOW INCLUDING LAST PART OF Nx4 DP with space optimisation ****
#include
using namespace std;
//Memoization
int f(int idx, bool buy, int cap, vector &prices, int &n, vector &dp){
//Base Cases
if(idx == n || cap == 0)return 0;
if(dp[idx][buy][cap] != -1)return dp[idx][buy][cap];
//Explore all paths
if(buy){
return dp[idx][buy][cap] = max( -prices[idx] + f(idx+1, 0, cap, prices, n, dp), 0 + f(idx+1, 1, cap, prices, n, dp));
}
return dp[idx][buy][cap] = max( prices[idx] + f(idx+1, 1, cap-1, prices, n, dp), 0 + f(idx+1, 0, cap, prices, n, dp));
}
int maxProfit(vector& prices, int n)
{
vector dp(n, vector(2, vector(3,-1)));
return f(0, 1, 2, prices, n, dp);
}
//Tabulation
int maxProfit(vector& prices, int n)
{
vector dp(n+1, vector(2, vector(3,0)));
for(int idx = n-1; idx>=0; idx--){
for(int buy = 0; buy=0;idx--){
for(int ts = 3;ts>=0;ts--){
if(ts%2==0){
cur[ts] = max(-prices[idx]+ahead[ts+1],ahead[ts]);
}
else{
cur[ts] = max(prices[idx]+ahead[ts+1],ahead[ts]);
}
}
ahead = cur;
}
return ahead[0];
}
int main()
{
return 0;
}
Space Optimised Code :-
int maxProfit(vector&price){
int n = price.size();
vector next(5,0),curr(5,0);
for(int i=n-1; i>=0; i--){
for(int tran = 3; tran>=0; tran--){
int profit = 0;
if(tran&1)
profit = max(price[i] + next[tran+1], next[tran]);
else
profit = max(-price[i] + next[tran+1], next[tran]);
curr[tran] = profit;
}
next = curr;
}
return next[0];
}
this series made our life easier. thanks striver
4 Solution mentioned (Memoized CODE , Tabulation code , Space Optimized with 2 Array ,Space Optimized with 1 D array )
I ❤ you Striver.
Memoized CODE :-
class Solution {
public:
int recur(int i,int trans,vector & nums,int n, vector& dp)
{
if(i == n || trans == 4)return 0;
if(dp[i][trans] != -1)return dp[i][trans];
if(trans % 2 == 0)
{
return dp[i][trans] = max(-nums[i] + recur(i+1,trans+1,nums,n,dp) , recur(i+1,trans,nums,n,dp));
}
else
{
return dp[i][trans] = max(nums[i] + recur(i+1,trans+1,nums,n,dp) , recur(i+1,trans,nums,n,dp));
}
}
int maxProfit(vector& prices) {
int n = prices.size();
vector dp(n,vector (4,-1));
return recur(0,0,prices,n,dp);
}
};
================================================================================================
Tabulation code :-
class Solution {
public:
int maxProfit(vector& nums) {
int n = nums.size();
vector dp(n+1,vector (5,0));
for(int i=n-1;i>=0;i--)
{
for(int trans = 3;trans >= 0;trans--)
{
if(trans % 2 == 0)
{
dp[i][trans] = max(-nums[i]+dp[i+1][trans+1],dp[i+1][trans]);
}
else
{
dp[i][trans] = max(nums[i] + dp[i+1][trans+1] , dp[i+1][trans]);
}
}
}
return dp[0][0];
}
};
==================================================================================================
Space Optimized with 2 Array :-
class Solution {
public:
int maxProfit(vector& nums) {
int n = nums.size();
vector next(5,0);
for(int i=n-1;i>=0;i--)
{
vector curr(5,0);
for(int trans = 3;trans >= 0;trans--)
{
if(trans % 2 == 0)
{
curr[trans] = max(-nums[i]+next[trans+1],next[trans]);
}
else
{
curr[trans] = max(nums[i] + next[trans+1] , next[trans]);
}
}
next = curr;
}
return next[0];
}
};
=================================================================================================
Space Optimized with 1 D array:-
class Solution {
public:
int maxProfit(vector& nums) {
int n = nums.size();
vector next(5,0);
for(int i=n-1;i>=0;i--)
{
for(int trans = 0; trans
Bhai 1d ya 2d array se space kaise optimize ho rha hain auxilary stack toh 0(n) hi hoga na abhi bhi ???
@@businessburstx Ha time complexity same hai..but 1d array me bhi possible hai solution
Code for the last approach:
Memoization:
int help(int i,int t,vector &prices,vector &dp)
{
if(t==4)return 0;
if(i==prices.size())return 0;
if(dp[i][t]!=-1)return dp[i][t];
if(t%2==0)
return dp[i][t]=max(-prices[i]+help(i+1,t+1,prices,dp),help(i+1,t,prices,dp));
else
return dp[i][t]=max(prices[i]+help(i+1,t+1,prices,dp),help(i+1,t,prices,dp));
}
int maxProfit(vector& prices) {
int n=prices.size();
vector dp(n,vector (4,-1));
return help(0,0,prices,dp);
}
Tabulation
int maxProfit(vector& prices) {
int n=prices.size();
vector dp(n+1,vector (5,0));
for(int i=n-1;i>=0;i--)
{
for(int t=0;t=0;i--)
{
for(int t=0;t=0;i--)
{
for(int t=0;t
DP(N x 4) Space Optimization Soln:
int maxProfit(vector& prices) {
int n = prices.size();
vector after(5,0) , curr(5,0);
for(int ind = n-1;ind>=0;ind--){
for(int trans = 3;trans>=0;trans--){
int profit;
if(trans % 2 == 0) // buy
profit = max(-prices[ind] + after[trans+1] ,
after[trans]);
else
profit = max(prices[ind] + after[trans+1] ,
after[trans]);
curr[trans] = profit;
}
after = curr;
}
return after[0];
}
note! 17:50 it is cap and buy can be anything
Fun fact, it doesn't matter if you return ahead[1][2], or cur[1][2] here, both of them get submitted.
thats not even funny
understood
Best Series for Stock Problems ,Love it.
int n=price.size();
vector after(4+1,0);
vector curr(4+1,0);
for(int ind=n-1;ind>=0;ind--){
for(int trans=3;trans>=0;trans--){
if(trans%2==0) curr[trans]=max(-price[ind]+after[trans+1], after[trans]);
else curr[trans]=max(price[ind]+after[trans+1],after[trans]);
}
after=curr;
}
return after[0];
did without even watching video. all credit goes to you bro thanks :)
@takeUforward Striver Sir!
only two condition are required for base case conditon for tabulation !!!
dp[n][0][0] = dp[n][1][0] = 0;
did the whole question by myself
Understood everything.
Here is the space-optimized code you asked for:
class Solution {
public:
int maxProfit(vector& prices) {
int n = prices.size();
int cap = 2;
bool buy = true;
vector t(n+1, vector(5, 0));
vector prev(5, 0), cur(5, 0);
for(int i=n-1; i>=0; i--){
for(int j=0; j
Able to solve using the concept of prev. problem. Thanks Striver!!
Understood. Solved the problem by myself. Great teaching striver
great explanation sir
Ultimate explanation 👍👍
Understood
how can i able to see the notes of this perticular problem inorder to revise the logic behind it. please help me anyone
Solution with space optmisation :=>
class Solution
{
public:
int maxProfit(vector& nums)
{
int n = nums.size();
vectorPrev(5 , 0);
vectorCurr(5 , 0);
for(int i = n - 1; i >= 0; i--)
{
for(int parity = 3; parity >= 0; parity--)
{
if(parity & 1)
{
int Sell_Here = nums[i] + Prev[parity + 1];
int Do_Not_Sell_Here = 0 + Prev[parity];
Curr[parity] = max(Sell_Here , Do_Not_Sell_Here);
}
else
{
int Buy_Here = -nums[i] + Prev[parity + 1];
int Do_Not_Buy_Here = 0 + Prev[parity];
Curr[parity] = max(Buy_Here , Do_Not_Buy_Here);
}
}
Prev = Curr;
}
return Prev[0];
}
};
can u do bottom up for this approach or bottom-up is not possible?
understood thank you
Hey Striver I have solved it using the concept that you taught at the last but I have solved for maximum k transactions instead of two. And I have space optimized it to a single 1D vector of size 2*k+1
Here is the space optimized code :-
int maximumProfit(vector &prices, int n, int k)
{
vector cur(2*k+1,0);
for(int transaction=0;transaction=0;index--)
{
for(int transaction=0;transaction
Thanks budddy
bro why u are doing this
for(int transaction=0;transaction if(transaction%2==1)
cur[transaction]=prices[n-1];
able to solve this probelm on own...thanks for ur hardwork...
tabulation with space optimisation:-
int maxProfit(vector& prices, int N)
{ n=N;
vector curr(5, -1);
vector aft(5, -1);
int buy =1;
for(int i=n;i>=0;i--){
for(int count=0;count
NUV DEVUDIVI SAAMI🙏🙇🙇🙇
Thank you Striver Sir for such a amazing DP series...
Welcome
last solution was impossible for me to think.. awesome😁🤐
why doesnt the space optimized code doesn't work in java using arrays instead of vector?
Solution for the other way:
Memoization:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
def f(ind,arr,trans):
if ind==len(arr) or trans==4:
return 0
if dp[ind][trans]!=-1:
return dp[ind][trans]
if trans%2==0:
profit=max(-arr[ind]+f(ind+1,arr,trans+1),f(ind+1,arr,trans))
else:
profit=max(arr[ind]+f(ind+1,arr,trans+1),f(ind+1,arr,trans))
dp[ind][trans]=profit
return profit
dp=[[-1 for i in range(4)]for j in range(len(prices))]
return f(0,prices,0)
Tabulation:
class Solution:
def maxProfit(self, n : int, price : List[int]) -> int:
# code here
dp=[[0 for i in range(4+1)]for j in range(n+1)]
for ind in range(n-1,-1,-1):
for trans in range(3,-1,-1):
if trans%2==0:
dp[ind][trans]=max(-price[ind]+dp[ind+1][trans+1],dp[ind+1][trans])
else:
dp[ind][trans]=max(price[ind]+dp[ind+1][trans+1],dp[ind+1][trans])
return dp[0][0]
Space Optimization:
class Solution:
def maxProfit(self, n : int, price : List[int]) -> int:
prev=[0]*(5)
for ind in range(n-1,-1,-1):
curr=[0]*(5)
for trans in range(3,-1,-1):
if trans%2==0:
curr[trans]=max(-price[ind]+prev[trans+1],prev[trans])
else:
curr[trans]=max(price[ind]+prev[trans+1],prev[trans])
prev=curr
return prev[0]
thankyou.
you made 3d dp so simple nd easy
Understood!!!! Thank you so much Striver.
I have done this question on my own thank you, striver
Understood !
in any case you are looking for the java solution :)
Space optimization:
class Solution {
private int helper(int[] prices , int ind , int buy , int cap , int dp[][][]){
if(ind == prices.length || cap == 0) return 0;
if(dp[ind][buy][cap] != -1) return dp[ind][buy][cap];
int profit = 0;
if(buy == 1){
profit = Math.max(-prices[ind] + helper(prices , ind+1 , 0 , cap ,dp) , helper(prices , ind+1 , 1 , cap ,dp));
}else{
profit = Math.max(prices[ind] + helper(prices, ind+1 , 1 , cap-1 ,dp) , helper(prices , ind+1 , 0 ,cap , dp));
}
return dp[ind][buy][cap] = profit;
}
public int maxProfit(int[] prices) {
int n = prices.length;
int dp[][][] = new int[n][2][3];
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < 2 ; j++){
for(int k = 0 ; k < 3 ; k++){
dp[i][j][k] = -1;
}
}
}
return helper(prices , 0 , 1 , 2 , dp);
}
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Tabulation:
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int dp[][][] = new int[n+1][2][3];
for(int ind = n-1 ; ind >= 0 ; ind--){
for(int buy = 0 ; buy < 2 ; buy++){
for(int cap = 1 ; cap < 3 ; cap++){
int profit = 0;
if(buy == 1){
profit = Math.max(-prices[ind] + dp[ind+1][0][cap] ,dp[ind+1][1][cap]);
}else{
profit = Math.max(prices[ind] + dp[ind+1][1][cap-1] , dp[ind+1][0][cap]);
}
dp[ind][buy][cap] = profit;
}
}
}
return dp[0][1][2];
}
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Space optimization:
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int dp[][] = new int[2][3];
for(int ind = n-1 ; ind >= 0 ; ind--){
int curr[][] = new int[2][3];
for(int buy = 0 ; buy < 2 ; buy++){
for(int cap = 1 ; cap < 3 ; cap++){
int profit = 0;
if(buy == 1){
profit = Math.max(-prices[ind] + dp[0][cap] ,dp[1][cap]);
}else{
profit = Math.max(prices[ind] + dp[1][cap-1] , dp[0][cap]);
}
curr[buy][cap] = profit;
}
}
dp = curr;
}
return dp[1][2];
}
}
Understood 🙏
Done with my own sir 😎thankyou and god bless you 🥰
i came up with the solution with similar to second method 27:02
bro not only your explanations are great but you write beautiful code I don't know why my code never look beatiful
thankyou so much sir
I have gone through this problem using the way Tushar roy has thought now that is good no doubt but the way striver has done it I really don't need to remember anything.
Understood !!!!!!!!!!!
Space Optimized Code for Second Aproach As Discussed in Last.
int maxProfit(vector& arr, int n)
{
vector next(5,0);
vector dp(5,0);
for(int i=n-1;i>=0;i--){
for(int k=0;k
You can also optimize this to Single Array
int maxProfit(vector &prices)
{
int n = prices.size();
vector dp(5, 0), temp(5, 0);
// base case
// just initialize the linear dp with 0
for (int index = n - 1; index >= 0; index--)
{
for (int transaction = 3; transaction >= 0; transaction--)
{
int profit;
if (transaction % 2 == 0)
{
int buying = -prices[index] + dp[transaction + 1];
int not_buying = 0 + dp[transaction];
profit = max(buying, not_buying);
}
else
{
int selling = prices[index] + dp[transaction + 1];
int not_selling = dp[transaction];
profit = max(selling, not_selling);
}
dp[transaction] = profit;
}
// dp = temp;
}
return dp[0];
}
@striver bhai yeh same memoization approach Sahil Srivastav ne apne bootcamp me samjhaya tha.. I'm just curious, did you guys had a common teacher who taught approach to you guys or you both have same thought process? 🤔
Ps- First viewer!
Its simple DP, aisa kisine banaya ni h bro approach ki uska stamp lg jaega :P
Also am not sure if space optimisation log pdha rhe h ki nai.
@@takeUforward, simple DP 😱😱😱, bhai ek time tha ki DP se darte the.. abhi tumhara, Sahil Srivastav, Aditya Verma ke wajah se lagta hai hum bhi DP kar lenge!
Yep only recursion, memoization approach was explained in Sahil's bootcamp. Space optimization is your trademark!
PS- Have some sleep bro.. Mental health is important too, can cause problems in older age if not taken care.. I understand mental tiredness caused due to ofc work + after ofc hours study(content creation in your case)
@@takeUforward bhahiya lis pr banaho na
Hi Stiver.. amazing explanation..
One doubt :
Top-down
-----------------
you usually go from n-1 to 0 in "Top-Down" but here you are starting from 0
Bottom-Up
-----------------
you usually go from 0 -> n-1 and go incrementally and last cell is answer
On stock series this seems quite opposite to me.
"Top-Down" does not mean that you will always go from n-1 to 0. You can also go from 0 to n-1. It all depends on you how you want to solve the question.
@@tanuagrawal9921 class Solution {
static int find(int n,int arr[],boolean buy,int days){
if(days
Understood, sir. Thank you very much.