Author Code (Kamonasish Roy) :

Iterative DP method

#include<bits/stdc++.h>
using namespace std;
const long long M=2e5+10,MOD=2000000007;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--){
int n;
cin>>n;
vector<vector<int>>dp(4,vector<int>(n+2,-1e9));
dp[1][0]=dp[2][0]=dp[3][0]=0;
vector<int>a(n+1),b(n+1),c(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)cin>>c[i];
for(int i=1;i<=n;i++){
dp[1][i]=max(dp[2][i-1],dp[3][i-1])+a[i];
dp[2][i]=max(dp[1][i-1],dp[3][i-1])+b[i];
dp[3][i]=max(dp[1][i-1],dp[2][i-1])+c[i];
}
cout<<max({dp[1][n],dp[2][n],dp[3][n]})<<"\n";
}
return 0;
}
Tester Code(Jahirul Islam Hridoy) :
Recursive DP Method
const int mx = 1e5 + 5 ;
ll n , a[mx] , b[mx] , c[mx] , dp[mx][3];
ll heart(ll pos , int arr){
if(pos > n) return 0 ;
if(dp[pos][arr] != -1) return dp[pos][arr] ;
ll res = INT_MIN ;
if(arr == 0) {
res = max(res , heart(pos + 1 , 1) + b[pos]) ;
res = max(res , heart(pos + 1 , 2) + c[pos]) ;
}
else if(arr == 1) {
res = max(res , heart(pos + 1 , 0) + a[pos]) ;
res = max(res , heart(pos + 1 , 2) + c[pos]) ;
}
else {
res = max(res , heart(pos + 1 , 1) + b[pos]) ;
res = max(res , heart(pos + 1 , 0) + a[pos]) ;
}
return dp[pos][arr] = res ;

}
void solve()
{
cin >> n ;
for(int i = 1 ; i <= n ; i++) cin >> a[i] ;
for(int i = 1 ; i <= n ; i++) cin >> b[i] ;
for(int i = 1 ; i <= n ; i++) cin >> c[i] ;
for(int i = 1 ; i <= n ; i++) dp[i][0] = dp[i][1] = dp[i][2] = -1;
cout << max({heart(1 , 0) ,heart(1 , 1), heart(1 , 2)}) << endl ;
}
int main()
{
Heart
int t ; cin >> t ; while(t--) solve() ;
}