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 <[email protected]> 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 <[email protected]> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
