Consultas Teórico/Práctico

Hola Valentina,

antes de pasar al tiempo te hago algunos comentarios de la solución que está bastante bien.

- veo que te falta un paso base en la "dirección de la d" (podría ser opt(0, i) = 0 ? ),
ya que le estas restando 1 a la d y en algún momento tiene que detenerse.
Siempre tener en cuenta los pasos bases que en caso de matrices suelen ser dos (la fila cero y la columna cero o algo similar),

- revisa el termino p(i,j) que no esta bien definido aunque anda cerca

Con respecto al tiempo de ejecución te comento lo siguiente:

si la implementación se hace de forma iterativa, se trata de recorrerla estructura OPT sea matriz o vector,
siempre calculando primero los valores "anteriores". En este caso el acceso a las entradas "anteriores"
de la matriz/vector es O(1). A esto hay que sumarle el tiempo del cálculo que se hace en cada celda si depende del tamaño de la entrada.

si la implementación es recursiva hay que asegurarse de que un mismo valor que ya
se calculó antes no se vuelva a calcular (lo que puede dar un peor caso exponencial) por eso hay que "recordarlo".
Esto se explica bien en la sección del libro que mencionas.
Recordando los valores y acotando la cantidad de llamadas recursivas
(puede ser con la medida de progreso de que en cada llamada se llena por lo menos una nueva entrada de la matriz de memoria si)
podemos acotar el tiempo de ejecución.

Recomendamos la versión iterativa pero se aceptan ambas.