I guess it doesn't require a DP, I might have understood your question
wrongly but from what I have understood solution is as follows :
S = sum at a particular point
A[N] = array which contains guard's respective demands
i = 0, S=0;
while (i < N)
{
if (A[i] >= S)
{
S += A[i];
}
i++;
}
On Mon, Feb 4, 2013 at 5:54 PM, marti <[email protected]> wrote:
> You have N guards in a line each with a demand of coins.You can skip paying
> a guard only if his demand is lesser than what you have totally paid before
> reaching him.Find the least number of coins you spend to cross all guards.
> I think its a DP problem but cant come up with a formula.Another approach
> would be to binary search on the answer but how do I verify if no. of coins
> is a possible answer?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
--
navneet singh gaur
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
