This is an interesting and easy DP problem. I solved this in less than 5 minutes.(Trust me ! Its that easy)
Let
dp[i] –> maximum coin sum till i monsters
dp[i]=max(arr[i]+solve(i+2),solve(i+1));
Case 1:
if you choose the ith monster’s coins you cannot choose the next so you
move to the i+2th monster.
Case 2:
if you do not choose the ith monster’s coins you still have a chance to choose i+1th monster’s coins.So you move to i+1th monster
[gist https://gist.github.com/anonymous/8433780]