DP problem set 1 Vacation question

#1

I am getting TLE by doing this question by recursion and dp

heres the code:

#include<bits/stdc++.h>
using namespace std;

struct activity{
int A, B, C;
};

int hello1( int i, vectorv , int n );
int hello2( int i , vectorv , int n );
int hello3( int i , vectorv , int n );
int n;
int dp[100001][3];

int hello1( int i, vectorv , int n )
{

if(i == n)
   return 0;


if(dp[i][0]!=INT_MAX )
   return dp[i][0];


dp[i][0]  = v[i].A + max( hello2(i+1, v , n), hello3(i+1 , v , n) );

return   dp[i][0] ;

}

int hello2( int i , vectorv , int n)
{
if(i == n)
return 0;

if(dp[i][1] != INT_MAX )
   return dp[i][1];

dp[i][1]= v[i].B + max( hello1(i+1 , v, n), hello3(i+1 , v, n));

return dp[i][1] ;

}
int hello3( int i, vectorv ,int n)
{
if(i == n)
return 0;

if( dp[i][2] != INT_MAX )
   return dp[i][2];
  
dp[i][2] = v[i].C + max( hello2(i+1, v,n), hello1(i+1 , v,n));

return dp[i][2];

}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

cin>>n;
vector<activity>v;

for(int i = 0; i<n; i++)
{
     int x, y, z;
     cin >> x >> y >> z;
     v.push_back( {x,y,z} );
}

for(int i=0 ;i <=n;i++)
for(int j=0;j<3;j++)
  dp[i][j]=INT_MAX;

int ans = max(hello1(0, v , n), max(hello2(0, v, n),hello3(0, v, n)) );
/*for(int i=0;i<n;i++)
{
    for(int j=0;j<3;j++)
    cout<<dp[i][j]<<" ";
    cout<<endl;
}*/
cout<<ans<<endl;

}

#2

Share your code using ide.codingblocks.com

#4

take this code for reference

#5

here the link
https://ide.codingblocks.com/s/370160

#6

Sir , I have done by this method it is running successfully but by recursion dp it is giving tle I have given my code link above

#7

have you submitted it anywhere?

#8

yes sir the recursion dp solution I have submitted at Atcoder site ,
it is running succesfully for 4 test cases but for other cases it is giving TLE .

#9

Try submitting this code and let me know if it passes test case or not

#10

yes sir with vector with 1 base index it is running successfully

#11

Then take reference from this code, if found any difficulty can ask me for sure :smile:

#12

sir I have taken reference but I have done it using recursion DP but it is giving TLE .
I have share my code link above can you tell why it is not working.

#13
#14

your logic is applicable but the implementation you have used is not right, see this detailed description
dp[i][0] will store the maximum points we can gain by doing activity A on day i.
dp[i][1] will store the maximum points we can gain by doing activity B on day i.
dp[i][2] will store the maximum points we can gain by doing activity C on day i.

Our base cases will be:

// If you swim in the sea in sea on the first day, you cannot get more than a[0] points.
dp[0][0] = a[0]; 
// If you catch bugs in the mountains on the first day, you cannot get more than b[0] points.
dp[0][1] = b[0]; 
// If you do homework at home on the first day, you cannot get more than c[0] points.
dp[0][2] = c[0];

For every day i , as we cannot do the activity we did on the previous day,

// If we do activity A today, we have to have done activities B or C on the previous day.
dp[i][0] = a[i] + max(dp[i - 1][1], dp[i - 1][2]); 

// If we do activity B today, we have to have done activities A or C on the previous day.
dp[i][1] = b[i] + max(dp[i - 1][0], dp[i - 1][2]);

// If we do activity C today, we have to have done activities A or B on the previous day. 
dp[i][2] = c[i] + max(dp[i - 1][1], dp[i - 1][0]);

Simply by checking for each day i , we can calculate the best we can do by the end of our last day.
As we can end by doing activities A, B, or C, our answer will be the maximum points gained on doing activities A, B, or C on the last day.
Time complexity: O(n)

1 Like
#15

If your doubt has been cleared, please mark it as resolved :smile:

#16

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.