Este problema es similar al problema de cambio de moneda.
Deje que dp [m] sea el número mínimo de monedas de las denominaciones d1, d2, …, dk necesarias para realizar cambios en la cantidad de C. En la solución óptima para realizar un cambio para la cantidad m, debe existir alguna primera moneda di, donde di <C. Además, las monedas restantes en la solución deben ser la solución óptima para realizar el cambio para (C-di).
Por lo tanto, si di es la primera moneda en la solución óptima para realizar un cambio para la cantidad m, entonces
dp [C] = 1 + dp [C – di] es decir, una moneda más dp [C – di] monedas para realizar un cambio óptimo para la cantidad (C – di).
No sabemos qué moneda es di, por lo que verificamos todas las posibilidades (sujeto a la restricción de que di <m), y el valor de la solución óptima debe corresponder al valor mínimo de 1 + dp [C – di].
Caso base dp [0] = 0
Recurrencia final:
dp [p] = 0 si C = 0
sino min (i: di 0
PD: El editorialista había olvidado mencionar la restricción de di <C en el editorial.
También puede probar esta pregunta SPOJ.com – Problema NFURY. Concepto similar
- ¿Es correcto mi nuevo estado de ánimo? Ingresé a la programación desde un punto de vista de programación algorítmica y, como tal, tengo una inclinación a querer saber cómo funcionan las cosas debajo. Pero ahora, después de un tiempo en el mundo de los desarrolladores, finalmente tengo que darme cuenta de que se trata menos de eso. ¿Lo que usted dice?
- ¿Cuál es el algoritmo utilizado para convertir cadenas en enteros?
- ¿Hay algún conocimiento de programación que pueda utilizar / ayudaría a aprender ajedrez?
- ¿Cuál es el mejor algoritmo de extracción de características para comparar dos imágenes?
- ¿Cómo dirigen los sistemas de guía del vehículo de lanzamiento la carga útil hacia órbitas tan precisas?
