He estado trabajando en el siguiente problema de este libro .
Un cierto lenguaje de procesamiento de cadenas ofrece una operación primitiva que divide una cadena en dos partes. Como esta operación implica copiar la cadena original, se necesitan n unidades de tiempo para una cadena de longitud n, independientemente de la ubicación del corte. Supongamos, ahora, que quiere romper una cadena en muchas partes. El orden en que se realizan los descansos puede afectar el tiempo total de ejecución. Por ejemplo, si desea cortar una cadena de 20 caracteres en las posiciones y , entonces hacer el primer corte en la posición incurre en un costo total de , mientras que hacer la posición 10 primero tiene un mejor costo de .
Necesito un algoritmo de programación dinámico que, dado cortes, encuentre el costo mínimo de cortar una cadena en piezas.