0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) should be 0.5 ( G(h - 1, i - 1) + G(h
- 1, i+1) )
i am not clear why the parents of a cup in upper row are consecutive?
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 10:43 AM, Gene <gene.ress...@gmail.com> wrote:
> G is just a helper function. You can "in line" this function and
> eliminate it.
>
> When you do this, you'll end up with
>
> F(h, i) = 0.5 * (l + r)
> where l = F(h-1,i-1) - C if 0 <= i-1 <= h-1 and F(h-1,i-1) > C else
> 0
> and r = F(h-1,i) - C if 0 <= i <= h-1 and F(h-1,i) > C else 0
>
> Here l is the left parent's outflow and r is the right parent's.
>
> So you are always computing the h'th row in terms of the (h-1)'th.
> For many DPs this means you'll need 2 row buffers. In this one you
> only need 1 element back in the current row. You can save this element
> in a single variable and get by with one buffer. I.e. note l for a
> given value of i is always the previous value of r. And for i=0, l is
> always 0 because there is no left parent.
>
> So you end up with
>
> f[0] = L; // fill in the first row
> for (ih = 1; ih <= h; ih++) { // loop thru rest of rows
> double l = 0; // left parent outflow at ii=0 is always 0.
> for (ii = 0; ii <= ih; ii++) { // loop thru columns
> // new right parent outflow
> double r = (ii < ih && f[ii] > C) ? f[ii] - C : 0;
> f[ii] = 0.5 * (l + r);
> l = r; // right parent is left of next row entry
> }
> }
> return (0 <= i && i <= h) ? f[i] : 0;
>
> This is doing the same as Dave's code for all practical purposes. It's
> untested but ought to work.
>
> On Feb 27, 10:05 pm, Ashish Goel <ashg...@gmail.com> wrote:
> > Gene, your DP is what i was thinking of but in code i could not coreleate
> > G(h - 1, i - 1) + G(h - 1, i) part (:
> > Best Regards
> > Ashish Goel
> > "Think positive and find fuel in failure"
> > +919985813081
> > +919966006652
> >
> >
> >
> >
> >
> >
> >
> > On Tue, Feb 28, 2012 at 7:50 AM, Gene <gene.ress...@gmail.com> wrote:
> > > G(h - 1, i - 1) + G(h - 1, i)
>
> --
> 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.
>
>
--
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.
