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 <amritsa...@gmail.com> 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 algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
