La idea básica de la programación dinámica es bastante directa. Para ser bueno en DP, esencialmente necesita sentirse cómodo con esta idea, y luego se trata de practicar. Daré algunas técnicas explicando cómo se te ocurre una solución DP para algunos problemas clásicos de DP:
La idea básica es que necesita encontrar un subproblema con una estructura similar al problema que está tratando de resolver. Por lo general, no hay muchas maneras de hacerlo, y solo teniendo en cuenta todas las posibilidades le da la solución.
Veamos algunos ejemplos:
- ¿Las estructuras de datos son más importantes o es el lenguaje?
- ¿Cuál es el mejor algoritmo para encontrar la ruta más corta en un gráfico orientado, donde algunos bordes están bloqueados y las teclas están en algún lugar de los nodos?
- ¿Qué tan bien funciona el algoritmo NativeTrack de AppsFlyer?
- ¿Qué tan complejos son los algoritmos que usan los sitios web de citas como eHarmony para unir a las personas?
- ¿Cuáles son las ventajas y desventajas de comparar la búsqueda de árboles de Monte Carlo y la programación dinámica aproximada?
- Problema de cambio de moneda: dado un valor [matemático] N [/ matemático], si queremos hacer un cambio para [matemático] N [/ matemático] centavos, y tenemos un suministro infinito de cada uno de [matemático] S = {S_1, S_2 , .., S_m} [/ math] monedas valoradas, ¿de cuántas maneras podemos hacer el cambio? El orden de las monedas no importa.
¿Cómo procedes? Claramente, el problema tiene dos dimensiones: el valor [matemática] N [/ matemática] y los tipos de monedas. Si [math] N [/ math] fuera pequeño como 1, o hubiera un solo tipo de moneda, la respuesta sería trivial. Por lo tanto, sus subproblemas tendrán una [matemática] N [/ matemática] más pequeña o menos tipos de monedas, o ambas.
¿Cómo sabes cuál es? Consideremos el caso de las [matemáticas] N [/ matemáticas] más pequeñas. Digamos que la [matemática] N [/ matemática] dada fue 10. Ahora, si supiera de cuántas maneras puede hacer un cambio para un valor menor, digamos 8, puede encontrar eficientemente el no. de maneras de hacer cambios para 10? Tenga en cuenta que la palabra clave aquí es “eficientemente”: si no puede hacerlo de manera eficiente, DP es inútil. Ahora, usted extiende la pregunta anterior: si supiera de cuántas maneras puede hacer cambios para todos los valores de [math] N [/ math] más pequeños que 10, puede encontrar eficientemente el no. de maneras de hacer cambios para 10? Una forma en que cree que puede proceder es agregar el no. de formas de hacer cambios para [math] 10-S_1 [/ math], no. de formas de hacer cambios para [math] 10-S_2 [/ math],…, porque agregar una moneda a cada una de estas formas le daría una suma de 10. Sin embargo, esto es incorrecto, porque el orden de las monedas no es importante , entonces estarás contando en exceso. En particular, si [matemática] S_1 = 1 [/ matemática] y [matemática] S_2 = 2 [/ matemática], entonces [matemática] 10 – S_1 [/ matemática] incluye formas que incluyen monedas de denominación 2, y usted agregue 1 a estos para obtener 10. De manera similar, [matemática] 10 – S_2 [/ matemática] incluye formas que incluyen monedas de denominación 1, y agregará 2 a estas para obtener 10. Entonces hay un recuento repetido.
Vayamos a la siguiente dimensión: los tipos de monedas. Suponga que sabe cuántas formas hay de cambiar [matemáticas] N [/ matemáticas] usando monedas de denominaciones [matemáticas] {S_1, …, S_ {m-1}} [/ matemáticas]. ¿Puedes usar esto para generar el no. de maneras de hacer un cambio de N usando [math] {S_1, …, S_m} [/ math]? Claramente no.
Pero, si sabía cómo hacer un cambio para cualquier valor por debajo de [matemática] N [/ matemática] utilizando monedas [matemática] {S_1, …, S_ {m-1}} [/ matemática], puede obtener la respuesta. En particular, no. de formas de hacer cambios para [matemática] N [/ matemática] usando monedas [matemática] {S_1,…, S_m} [/ matemática] = no. de formas de hacer cambios para [math] N – S_m [/ math] usando monedas [math] {S_1,…, S_m} [/ math] + no. de formas de hacer cambios para [matemáticas] N [/ matemáticas] usando monedas [matemáticas] {S_1, …, S_ {m-1}} [/ matemáticas]. Tenga en cuenta que los dos términos anteriores son mutuamente excluyentes: el primer término corresponde a los casos en los que utiliza al menos una moneda de denominación [matemáticas] S_m [/ matemáticas], mientras que el segundo caso no incluye monedas de denominaciones [matemáticas] S_m [/ matemáticas].
Ahora, desde este punto, solo tiene que realizar el llenado de la tabla para obtener la respuesta.
- Problema de la ruta más corta de todos los pares: dado un gráfico, encuentre la ruta más corta desde cada vértice a cualquier otro vértice.
¿Qué puede reducir para reducir el tamaño del problema? El tamaño del gráfico, así que encuentre la ruta más corta desde el vértice i al j usando el subgrafo [math] {v_1, …, v_k} [/ math]. Y eso te da el algoritmo Floyd-Warshall.
- Problema de suma de subconjunto: dado un conjunto de enteros no negativos [matemática] S = {s_1,…, s_m} [/ matemática] y un valor [matemático] N [/ matemática], determine si hay un subconjunto de establecer [matemáticas] S [/ matemáticas] con una suma igual a [matemáticas] N [/ matemáticas].
Nuevamente, hay dos dimensiones: el tamaño del conjunto y [math] N [/ math]. Procediendo de manera similar al problema de cambio de monedas, debe usar subproblemas en ambas dimensiones: hay una manera de hacer [math] N [/ math] si hay una manera de hacer [math] N – s_m [/ math] usando [ matemática] {s_1, …, s_ {m-1}} [/ matemática], o si hay una manera de hacer [matemática] N [/ matemática] usando [matemática] {s_1, …, s_m} [/ matemática] . Esto tiene la misma interpretación que arriba: o [math] s_m [/ math] está incluido en la suma o no lo está.
A menudo, las personas comienzan pensando en estos casos mutuamente excluyentes, como la inclusión y la exclusión, lo que hace que sea complicado porque diferentes problemas tienen diferentes criterios para generar conjuntos mutuamente excluyentes. La forma correcta es comenzar a pensar en términos de dimensiones, que es mucho más consistente en todos los problemas.
Finalmente, recomendaría el libro Algorithm Design. Tiene un capítulo cada uno sobre varios paradigmas de algoritmos, como algoritmos codiciosos, programación dinámica, divide y vencerás, etc. Los ejercicios al final del capítulo son factibles en número y cubren problemas básicos y avanzados.
