Programming Kotlin: dynamic programming example speed up (Kindle Loc 9737)

@venkats

There is an example in Applying Memoization to Dynamic Programming chapter.
recursion/cutrod.kts, fragment below

    (1 until length).fold(priceAtLength){
        max, cutLength ->
        val cutPrice = maxPrice(cutLength) + maxPrice(length - cutLength)
        Math.max(cutPrice, max)
    }

cutPrice calculation effort is doubled here because of addition symmetry:
maxPrice(1) + maxPrice(6) is the same as maxPrice(6) + maxPrice(1)

The same result can be achieved by reducing computations to

    (1 until length/2).fold(priceAtLength){ ...

Regards
Krzysztof Bardzinski