@marti : can u please make problem statement clear .. give one example , we can understand clearly
On Tue, Feb 5, 2013 at 9:14 AM, immars <[email protected]> wrote: > 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. > > > -- 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.
