suppose: v : array of guards' request
P(n): our problem: least coin spent until guard n, according to these rules M(n, x): least coin possibly combined equal to or larger than x until guard n then: P(n) = min(P(n-1)+v[n], M(n-1, v[n])) M(n, x) = min(M(n-1, x), M(n-1, x-v[n]) + v[n]) On Monday, February 4, 2013 8:24:19 PM UTC+8, marti 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.
