I thought this was a very simple problem, but not so :-)

Compressed problem statement: Given a list of monsters with their dread score (scariness score) and the price to be paid for bribing, what is the total minimum bribe to be paid. Monster 1 has to be bribed. You bribe a monster and it becomes a part of your troop. You don't need to bribe monster[i] if the total scariness of the monsters with you exceed the scariness score of monster[i], otherwise you better be wise to bribe.

I get the idea that while maximizing the dread score, we need to minimize the total price. Interesting combination. What algo fits here? Found it - Dynamic programming. Now, it is time to understand, write code and get practice points :-)

Hey this works as well. Can you share ur DP solution.

ReplyDeleteclass MonstersValley2

{

public int minimumPrice(int[] dread, int[] price)

{

return minCoinStep(0, 0, 0, dread, price);

}

public int minCoinStep(int i,long s,int c,int[] d,int[] p)

{

if(i==d.length)return c;

if(d[i]>s)

return minCoinStep(i+1, s+d[i], c+p[i], d, p);

return Math.min(minCoinStep(i+1, s, c, d, p),

minCoinStep(i+1, s+d[i], c+p[i], d, p));

}

}

Hi Mihir,

ReplyDeleteHaven't coded it up yet. Will let you know shortly. Thank you for the comment.

-raghav