@immars , can you explain with some example or algorithm ? Thanks Shashank
On Tuesday, February 5, 2013 9:14:03 AM UTC+5:30, immars 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
