# Editorial to a nice dynamic programming problem on Codechef : -

Statement : -
(Note:-Here ‘J’ is considered as ‘1’ and ‘F’ is considered as ‘0’.

A nice problem to brush up the basics of dp .

We are given an array (A) of integers containing ‘1’ and ‘0’ . We are given one more array (B) containing the corresponding values.

Example :-

A : 0 1 0 1

B : 1 2 4 3

We have to traverse the given array in such a way so that we can get the maximum sum of values from array ‘ B’

But here is the twist , say, we pick up a value at index ‘x’ , now if the value at index ‘x+1’ is ‘1’ we can never pick it up!

Example (s) :-

1 1 0

7 8 9

We have 2 ways:-

1)7+9=16(We can’t pick up “8” )

2) 8+9=17 (As the next index is ‘0’)

Solution:-

(This is my trick to solve hard-dp-problems on 1-d-array)

Lets say, our array has only ‘3’ elements, then, if ;

DP[I] MEANS THE BEST SUM WE CAN GET TILL INDEX ‘I’

1. a[i]=0;

and a[i-1]=0;

then, we can eat both the elements, so

dp[i]=b[i]+b[i-1];

(lets eat both

1. a[i]=0;

and a[i-1]=1;

Again, first we will eat ‘1’, then ‘0’ , no restrictions!

So:-dp[i]=b[i]+b[i-1];

1. a[i]=1;

and a[i-1]=(1 OR 0)

Either we can eat up ‘1’ and sacrifice the previous element or we leave ‘1’ and stay happy with what we had previously

So,

dp[i]=max(b[i]+dp[i-2],dp[i-1])

Applying the above recurrence relations to the full array solves our problem

My implementation assumes ‘J’ as ‘ 1 ’ and ‘F’ as ‘ 0