How to solve this problem using dp?

general
1

@anon55659401 please help

3 Likes
2

I am too waiting for all submissions to become public.If anyone solved it,please post the solution here.

3

dp1[n] and dp2[n] are two dp-arrays.

for(i=3;i<=n-1;i++)
{

dp1[i]=max(a1[i]+dp2[i-1],a1[i]+a1[i-1]+dp2[i-2],a1[i]+a1[i-1]+a1[i-2]+dp2[i-3]);

dp2[i]=max(a2[i]+dp1[i-1],a2[i]+a2[i-1]+dp1[i-2],a2[i]+a2[i-1]+a2[i-2]+dp1[i-3]);

}

cout<<max(dp1[n-1],dp2[n-1]) ;

4 Likes
4

My idea was simple and recursive.
the state is (i, a, b)
where i is the index and a is how many consecutive can you take from first array from this index
and b is how many consecutive can you take from second array from this index
call with (0,3,3)
write recursion with memoization. done.

here’s my AC code

1 Like