Problem Link : - BUG2K18E Problem - 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’)
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’
- 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
- 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];
- 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 ’
Link : - Ideone.com
For clarity : - https://www.geeksforgeeks.org/ma…