Editorial to a nice dynamic programming problem on Codechef : -

Problem Link : - https://www.codechef.com/problems/BUG2K18E

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

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! :slight_smile:

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’)

Final answer :- 17

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 :slight_smile:

  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 :slight_smile:

So,

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

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

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

Link : - Ideone.com

For clarity : - https://www.geeksforgeeks.org/ma…