Dicen que no puede resolverse por medio de un algoritmo greedy y plantean una idea de contraejemplo. Esto es conceptualmente incorrecto: plantean una idea de un algoritmo greedy que no funciona, eso no significa que ningún algoritmo greedy puede obtener la solución óptima.
Justificación o explicación de cómo llegan a la ecuación de recurrencia: porfis creeme.
La ecuación de recurrencia parece estar planteada al revés: dependen de valores posteriores en vez de anteriores. Si bien funciona y es completamente correcto, no les recomiendo para nada afrontar problemas de programación dinámica de esta forma.
No es Memorización, es Memoización (detalle menor, pero lo menciono, memoization).
Como recomendación: separar la resolución de PD de la reconstrucción de la solución. Esto para asegurarse a nivel programático que cada función haga una cosa, y además para facilitar entender y analizar bien la complejidad de cada cosa. En este caso es medio obvia la complejidad del algoritmo de PD, pero el de la reconstrucción no es del todo obvio, y si lo es, como mínimo es interesante de mencionar cómo varía su comportamiento respecto a los valores de $s_i$ y $e_i$.
En particular, ustedes mencionan que esto es lineal. Si los valores de $s_i$ son muy grandes (es decir, conviene siempre entrenar), entonces efectivamente va a ser lineal (es el mejor caso posible), pero si $s_1$ es medianamente grande y $s_2$ es chico (y de allí para abajo), seguro va a terminar conviniendo intercalar entrenamientos con descansos, con lo cual hay que ir buscando máximos, terminando en algo peor que lineal. Corríjanme si me equivoco, es lo que entiendo así nomás del código, pero hay algo que no me termina de convencer de lo mismo que estoy leyendo yo.
Lo más importante de lo que marco son las primeras dos cosas.
Dicho esto, la nota del tp es 8.
Hola! Les dejo por acá las correcciones.
Lo más importante de lo que marco son las primeras dos cosas. Dicho esto, la nota del tp es 8.