On May 11, 3:49=A0pm, rossum <rossu...@[EMAIL PROTECTED]
> wrote:
> On Fri, 9 May 2008 03:48:20 -0700 (PDT), James Dow Allen
> <jdallen2...@[EMAIL PROTECTED]
> wrote:
> >the straightforward solution to this puzzle
> >is not of exponential complexity, but rather N^3/3.
>
> >I'm enclosing my source code (and cross-posting to
> >comp.lang.c) for critique.
> I think that you could use a better algorithm. =A0You are repeatedly
> calculating the cost of the same sticks as part of your subproblems.
No. Reread the source to see that the code calculates and saves the
intermediate results exactly as you describe. It is the caller of
bestcut()
rather than bestcut() itself that saves these results -- is that
where your confusion lies?
My algorithm is O(N^3). Are your comments intended to suggest
existence of a less complex algorithm?
James
