Algunos problemas no se resuelven de izquierda a derecha, porque la decisión que importa divide la entrada por el medio. Fusionar montones, cortar una tabla, tomar cartas de los dos extremos de una fila o conservar letras que se leen igual al revés: todos piden la mejor respuesta en un intervalo de start a end, y esa respuesta depende de intervalos más pequeños que hay dentro.
Define best[start][end] para un intervalo y después elige cómo se divide. Al fusionar, la última fusión une [start, mid] y [mid + 1, end]. Al cortar, el primer corte deja dos piezas independientes. En un juego de dos jugadores, quien mueve toma un extremo y el rival juega lo mejor posible con el resto. Cuando la primera acción cambia sus propios vecinos, elige en su lugar la última acción dentro del intervalo, porque sus vecinos están fijos.
Rellena los intervalos por longitud, de los más cortos a los más largos, o recorre start de derecha a izquierda para que cada intervalo interior esté listo. Con n^2 intervalos y hasta n divisiones en cada uno, cuenta con O(n^3) de tiempo y O(n^2) de espacio, que basta para unos cientos de elementos.
Resuelve primero los intervalos cortos; cada intervalo más largo prueba todas las divisiones.