Find the best order to take tiles from a row when each scores with its neighbours, or to merge neighbouring piles at the least cost: solve every stretch of the row by the item it deals with last, shortest stretches first. Θ(n³) for the table against 3ⁿ⁻¹ calls of plain recursion.
This interactive visualization needs JavaScript.