Alguns problemas não se resolvem da esquerda para a direita, porque a decisão que importa divide a entrada no meio. Fundir montes, cortar uma tábua, pegar cartas das duas pontas de uma fileira ou manter letras que se leem igual de trás para a frente: todos pedem a melhor resposta em um intervalo de start a end, e essa resposta depende de intervalos menores que estão dentro dele.
Defina best[start][end] para um intervalo e depois escolha como ele se divide. Ao fundir, a última fusão une [start, mid] e [mid + 1, end]. Ao cortar, o primeiro corte deixa duas partes independentes. Em um jogo de dois jogadores, quem joga pega uma ponta e o adversário joga da melhor forma com o restante. Quando a primeira ação muda os próprios vizinhos, escolha no lugar dela a última ação dentro do intervalo, porque seus vizinhos estão fixos.
Preencha os intervalos por tamanho, do menor para o maior, ou percorra start da direita para a esquerda para que todo intervalo interno esteja pronto. Com n^2 intervalos e até n divisões em cada um, conte com O(n^3) de tempo e O(n^2) de espaço, o que é suficiente para algumas centenas de itens.
Resolva primeiro os intervalos curtos; cada intervalo maior testa todas as divisões.