On Sun, 11 May 2008 02:51:38 -0700 (PDT), James Dow Allen
<jdallen2000@yahoo.com> wrote:

>On May 11, 3:49pm, rossum <rossu...@coldmail.com> wrote:
>> On Fri, 9 May 2008 03:48:20 -0700 (PDT), James Dow Allen
>> <jdallen2...@yahoo.com> 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. You 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 does indeed, my mistake. Thankyou for the correction.

>It is the caller of
>bestcut()
>rather than bestcut() itself that saves these results -- is that
>where your confusion lies?
Probably because I am more used to Java rather than C, and your
solution is expressed in procedural rather than OO terms.

>
>My algorithm is O(N^3). Are your comments intended to suggest
>existence of a less complex algorithm?
No. Since I thought you were recalculating intermediate results I
thought there was an obvious speed improvement that wasn't actually
there.

Apologies for my mistake.

rossum

>
>James