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