### rum3r's blog

By rum3r, history, 4 weeks ago,

What am I doing wrong in this problem?

inline void solve(){
ll n;
cin >> n;
ll a[n], b[n];
for(int i=0; i<n; ++i) {
cin >> a[i];
}
for(int i=0; i<n; ++i) {
cin >> b[i];
}
ll dp[3][n];
dp[0][0] = a[0];  //selecting first person
dp[1][0] = b[0];  //selecting second person
dp[2][0] = 0;     //not selecting anyone
for(int i=1; i<n; ++i) {
dp[0][i] = max(dp[1][i-1]+a[i], max(dp[2][i-1]+a[i], dp[2][i-1]+b[i])); //for first person
dp[1][i] = max(dp[0][i-1]+b[i], max(dp[2][i-1]+a[i], dp[2][i-1]+b[i])); //for second person
dp[2][i] = max(dp[0][i-1], dp[1][i-1]);  //for not selecting
}
cout << max(dp[0][n-1], dp[1][n-1]) << endl;  //taking max over all..
}


PROBLEM Any help would be appreciated.

• 0

 » 4 weeks ago, # |   +3 The problem is with your DP relation. In the final loop where you are filling in the states, In dp[0][i] you should not consider the case where you are choosing a person from the second row and similarly, In dp[1][i] you should not consider the case where you are choosing a person from the first row. Updated Correct Submission — Link
•  » » 4 weeks ago, # ^ |   +3 Thanks for giving your valuable time brother. I got it! I just want to ask, In tutorial how are they calculating the dp without array ??
•  » » » 4 weeks ago, # ^ |   0 You see that the ith states of our DP (dp[i]) depend only on the (i-1)st states (dp[i-1]). So Instead of storing the values of all the previous states in an array, In the tutorial, only the values to the previous state are being stored.
•  » » » » 4 weeks ago, # ^ |   +3 Thanks, Buddy you're the nicest person on CF that I have ever met. Thanks for your help. :D