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
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 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.
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.
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
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.
int recursion_new(int ind ,int trans,int n,vector&val) { if(trans==0) return 0; if(ind==n) return 0; int profit=0; if(trans%2==0) profit=max(-val[ind]+recursion_new(ind+1,trans-1,n,val),0+recursion_new(ind+1,trans,n,val)); else//avoid using increment and decrement operator, int place use +1 or -1 profit=max(val[ind]+recursion_new(ind+1,trans-1,n,val),0+recursion_new(ind+1,trans,n,val)); return profit; } int memo_new(int ind,int trans,int n,vector&val,vector &dp) { if(trans==0) return 0; if(ind==n) return 0; if(dp[ind][trans]!=-1)return dp[ind][trans]; int profit=0; if(trans%2==0) profit=max(-val[ind]+memo_new(ind+1,trans-1,n,val,dp),0+memo_new(ind+1,trans,n,val,dp)); else//avoid using increment and decrement operator, int place use +1 or -1 profit=max(val[ind]+memo_new(ind+1,trans-1,n,val,dp),0+memo_new(ind+1,trans,n,val,dp)); return dp[ind][trans]=profit; } int tabulation_new(int n,vector&val,vector&dp) { int profit=0; for(int ind=n-1;ind>=0;ind--)//bottom up approach { for(int trans=1;trans=0;ind--)//bottom up approach { for(int trans=1;trans
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.
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
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.
Home Work : 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 trans=0;trans
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);
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]
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" tabulation code for last approach: int maxProfit(vector& prices, int n) { // Write your code here. vectordp(n+1,vector(5,0)); for(int ind=0;ind
} } //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 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++){
**** 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];
@@nupur8804 Nope, I was getting tle before space optimisation, but not after that. My code: #include int maxProfit(vector&a) { int n=a.size(); vectorpre(2, vector(3,0)), cur(2, vector(3,0)); for(int i=n-1;i>=0;i--){ for(int j=0;j
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😃
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😂😂
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.
This is the first time i solved Leetcode hard myself because of u Striver. Thank u so Much for this kind of teaching.
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 ?
Recursion is magic ❤
and Striver is the magician 😂
@@rahulraj94391 🤣🤣
The only magician who teaches magic
predicted for first time the solution even its hard problem , Thankyou so much for providing conceptual understanding Striver
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
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
hi striver bhaiya i did this problem without even watching the video for a second using 3D dp. Thanks to u bhaiya
66.6% done ,
thanks striver broo to make me able to solve any of the dp pattern learn so far in this series.
understood bhaiya .this is your one of the best series bhaiya. thank you bhaiya
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
Understood!! Thank you so much bhaiya!!
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.
@takeUforward Striver Sir!
only two condition are required for base case conditon for tabulation !!!
dp[n][0][0] = dp[n][1][0] = 0;
Thank you very much for providing DP tutorials .
pls bring Next Series on Segment trees , fenwick tree .
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
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
Best Series for Stock Problems ,Love it.
Raj Vhaiya the technique using 4 variables is derived from Buy and Sell Stocks I.
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.
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
int recursion_new(int ind ,int trans,int n,vector&val)
{
if(trans==0)
return 0;
if(ind==n)
return 0;
int profit=0;
if(trans%2==0)
profit=max(-val[ind]+recursion_new(ind+1,trans-1,n,val),0+recursion_new(ind+1,trans,n,val));
else//avoid using increment and decrement operator, int place use +1 or -1
profit=max(val[ind]+recursion_new(ind+1,trans-1,n,val),0+recursion_new(ind+1,trans,n,val));
return profit;
}
int memo_new(int ind,int trans,int n,vector&val,vector &dp)
{
if(trans==0)
return 0;
if(ind==n)
return 0;
if(dp[ind][trans]!=-1)return dp[ind][trans];
int profit=0;
if(trans%2==0)
profit=max(-val[ind]+memo_new(ind+1,trans-1,n,val,dp),0+memo_new(ind+1,trans,n,val,dp));
else//avoid using increment and decrement operator, int place use +1 or -1
profit=max(val[ind]+memo_new(ind+1,trans-1,n,val,dp),0+memo_new(ind+1,trans,n,val,dp));
return dp[ind][trans]=profit;
}
int tabulation_new(int n,vector&val,vector&dp)
{
int profit=0;
for(int ind=n-1;ind>=0;ind--)//bottom up approach
{
for(int trans=1;trans=0;ind--)//bottom up approach
{
for(int trans=1;trans
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.
Understood
Happy Guru Purnima coding Guru 🙇
understood
Understood ❤
thankyou.
you made 3d dp so simple nd easy
Understood!!!! Thank you so much Striver.
#include
int maxProfit(vector& p, int n)
{
vector after(5,0);
vector cur(5,0);
for(int ind=n-1; ind>=0; ind--){
for(int t=3; t>=0; t--){
if(t%2==0){
cur[t] =max(-p[ind]+after[t+1],after[t]);
}
else{
cur[t]=max(p[ind]+after[t+1],after[t]);
}
}
after=cur;
}
return after[0];
}
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
// Using SPACE OPTIMIZATION (More Optimized)
#include
int solve(vector& prices,int n)
{
vector prev(5,0);
for(int i=n-1;i>=0;i--)
{
for(int trans=3;trans>=0;trans--)
{
if(trans%2==0) // BUY
prev[trans]=max(prev[trans+1]-prices[i],
0+prev[trans]);
else // SELL
prev[trans]=max(prices[i]+prev[trans+1],
0+prev[trans]);
}
}
return prev[0];
}
int maxProfit(vector& prices, int n)
{
return solve(prices,n);
}
UNDERSTOOD........Thank You So Much for this wonderful video......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Understood !
homework space optimized:
int sop(vector& prices)
{
int n=prices.size();
vector prev(4,0);//i==n B S B S
for(int ind=n-1;ind>=0;ind--)
for(int i=0;i
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.
Home Work : 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 trans=0;trans
Understood 🙏
Done with my own sir 😎thankyou and god bless you 🥰
Understood!
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
N * 4 DP array answer: (HOME WORK done) -
public class Solution {
public static int maxProfit(int[] prices) {
int len = prices.length;
int[] dp = new int[5];
for(int index = len - 1; index >= 0; index--) {
int[] temp = new int[5];
for(int transaction = 0; transaction < 4; transaction++) {
if(transaction % 2 == 0) {
int buying = -prices[index] + dp[transaction + 1];
int notBuying = dp[transaction];
temp[transaction] = Math.max(buying, notBuying);
}
else {
int selling = prices[index] + dp[transaction + 1];
int notSelling = dp[transaction];
temp[transaction] = Math.max(selling, notSelling);
}
}
dp = temp;
}
return dp[0];
}
}
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];
}
I realised today auxiliary stack space stands for ASS lol
instead of dp array of n * transactions, we can optimize it to dp of 2 * 3
Thanks to you sir...
vector dp (2,vector(3,0));
for(int i = n-1 ; i>= 0 ; i--){
for(int j = 1 ; j>= 0 ; j--){
for(int k = 1 ; k>=0 ; k--){
if(k){
dp[k][j] = max(prices[i] + dp[0][j+1],dp[1][j]);
}else{
dp[k][j] = max(-prices[i]+ dp[1][j],dp[0][j]);
}
}
}
}
return dp[0][0];
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]
The Nx4 solution is amazing and very intuitive. Thanks a lot for explaining multiple solutions to the same problem!
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
how can i able to see the notes of this perticular problem inorder to revise the logic behind it. please help me anyone
"understood"
tabulation code for last approach:
int maxProfit(vector& prices, int n)
{
// Write your code here.
vectordp(n+1,vector(5,0));
for(int ind=0;ind
Understood!! Thank you so much bhaiya!!
understood
Thank you for this 👌
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!
Fully 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
luved this one, great work sir
Tabulation code
int maxProfit(vector& prices, int n)
{
vector dp(n+1,vector (5,0));
for(int i=n-1;i>=0;i--){
for(int k=3;k>=0;k--)
{
int profit=0;
if(k%2==0)
profit=max((-prices[i]+dp[i+1][k+1]),dp[i+1][k]);
else
profit=max((prices[i]+dp[i+1][k+1]),dp[i+1][k]);
dp[i][k]=profit;
}
}
return dp[0][0];
}
Understood 😊
//space optimization-TC-O(4*n),SC-O(2*5)
vectorahead(5,0),curr(5,0);
//if(i==n || j==4) dp[i][j]=0 > already done while dp table declaration
for(int i=n-1;i>=0;i--){
for(int j=0;j
Understood
4 trike to bta hi diye , 1 aur bta dena tha 5 complete ho jate......you are amazing striver.....thankuuuuu
no words for your contribution to all DSA learner :-))))
Understood
NUV DEVUDIVI SAAMI🙏🙇🙇🙇
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
can u do bottom up for this approach or bottom-up is not possible?
Understood!!! Amazinggg
// tabulation t.c= O(n*4) s.c=O(n*5)
// vectordp(n+1,vector(5,0));
// for(int i=n-1;i>=0;i--)
// {
// for(int tran=3;tran>=0;tran--)
// {
// if(tran%2==0)
// dp[i][tran]=max(-price[i] + dp[i+1][tran+1],
// dp[i+1][tran]);
// else
// dp[i][tran]=max(price[i] +dp[i+1][tran+1],
// dp[i+1][tran]);
// }
// }
// return dp[0][0];
// space optimization t.c= O(n*4) s.c=O(2*5)
vectordp(5,0);
vectortemp(5,0);
for(int i=n-1;i>=0;i--)
{
for(int tran=3;tran>=0;tran--)
{
if(tran%2==0)
temp[tran]=max(-price[i] + dp[tran+1],dp[tran]);
else
temp[tran]=max(price[i] +dp[tran+1],dp[tran]);
}
dp=temp;
}
return dp[0];
**** 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;
}
Understood both ways dp[n][2][3] & dp[n][4] ❤
Understood :)
Done it almost by myself.
(Bhai pad le thoda, speed kaafi slow h ;-;)
Aug'1, 2023 09:47 pm
Hey i'm getting tle even after space optimization for the last case have you got tle as well?
@@nupur8804 Nope, I was getting tle before space optimisation, but not after that.
My code:
#include
int maxProfit(vector&a)
{
int n=a.size();
vectorpre(2, vector(3,0)), cur(2, vector(3,0));
for(int i=n-1;i>=0;i--){
for(int j=0;j
@@nupur8804was searching for same😢... did you resolve ?
With your guidance , i am able to solve all types of buy and sell stock problems.
watching this video finishes the stock pattern for me thanks a lot striver
Understood
Understood
In tabulation why is it n+1 and not n? since we are going from n-1 to 0 i.e n numbers, so it should have been n
Hey, I have the same question. Did you get the ans ?
@@radhikachaudhary2366 having same doubt
Why in tabulation, you are increasing n to n+1 in dp array?? but not in memoization code ? ?
US striver
Understood
Can someone explain why we are using a vector of size 3 for cap in memoization? I think we are not storing for cap=0?
understood
I am able to solve this on my own.....
class Solution {
public:
int maxProfit(vector& prices) {
int n = prices.size();
vector after(5 , 0) , cur(5 , 0);
for(int ind=n-1;ind>=0;ind--){
for(int trans = 0;trans
understood
Understood!
why doesnt the space optimized code doesn't work in java using arrays instead of vector?
Understood !!!!!!!!!!!
understood thank you
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😃
UNDERSTOOD
Understood Sir!
class Solution {
public:
int f(int ind,int tran,vector&prices,int n,vector&dp){
if(ind == n || tran==4){
return 0;
}
if(dp[ind][tran] != -1)
return dp[ind][tran];
if(tran%2 == 0){
return dp[ind][tran]=max(-prices[ind]+f(ind+1,tran+1,prices,n,dp),f(ind+1,tran,prices,n,dp));
}
return dp[ind][tran]=max(prices[ind]+f(ind+1,tran+1,prices,n,dp),f(ind+1,tran,prices,n,dp));
}
int maxProfit(vector& prices) {
int n=prices.size();
vectordp(n,vector(4,-1));
return f(0,0,prices,n,dp);
}
};
Thank You Sir, Understood :)
in the previous question he returned dp[0][1] but here why are we returning dp[0][0][2]? shouldn't it be dp[0][1][2]?
Understood
Tabulation::
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 t=0;t