Dave's code is good. Here is a more abstract way of thinking about it. Maybe helpful?
Number the rows starting at the top with h=0, and the left i=0. Then the parents of cup(h,i) are always cup(h-1,i-1) and cup(h-1,i). When h<0, i<0 or i >h, the parent does not exist. Let F(h, i) be the amount that has flowed in to cup(h,i) after L went in at the top and let G(h, i) be the amount that has flowed out. So note that what flowed out is either what flowed in minus C or else nothing if less than C has flowed in. It's also zero if cup(h,i) doesn't exist: G(h,i) = { F(h, i) - C if 0 <= i <= h and F(h, i) > C { 0 otherwise Now note that what flows in is equal to half of what flowed out of each parent unless we have the top cup, which means L flowed in! F(h, i) = { L if h = i = 0 { 0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) otherwise The answer we want is given by F. Dave's code is a nice implementation of this DP. On Feb 27, 5:23 pm, Dave <dave_and_da...@juno.com> wrote: > @Ashish: I didn't make any assumption that nothing comes from the > left. Does my code give the wrong answer? > > Dave > > On Feb 27, 10:36 am, Ashish Goel <ashg...@gmail.com> wrote: > > > > > > > > > Dave, why the assumption that nothing is coming from left side. > > > Every cup gets something from cup left above and right above itself when > > they have something extra? > > > Best Regards > > Ashish Goel > > "Think positive and find fuel in failure" > > +919985813081 > > +919966006652 > > > On Mon, Feb 27, 2012 at 8:17 PM, Dave <dave_and_da...@juno.com> wrote: > > > // nothing coming in from the > > > left -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.