Respuesta corta: prueba todo.
Respuesta más larga: esta es una habilidad que solo viene con experiencia. Hasta que tenga esa experiencia, será difícil, la única buena manera de aprender es probar muchas cosas y fracasar en la mayoría de ellas, pero hay algunas estrategias que pueden ayudar.
Primero, olvídate de los algoritmos codiciosos hasta que tengas un algoritmo de programación dinámico que funcione. Es increíblemente fácil crear estrategias ambiciosas que parezcan razonables pero que no resuelvan el problema por completo. Literalmente les digo a mis alumnos de algoritmos que escribir las letras g, r, e, e, d, y en ese orden es una instrucción inequívoca de su subconsciente para usar la programación dinámica.
- ¿Qué es un algoritmo para generar todas las combinaciones posibles de un conjunto dado de letras (por ejemplo, 'a', 'b', 'c', 'd', 'e')?
- ¿Cuáles son algunos de los recursos disponibles para los estudiantes de informática en predicción de la estructura secundaria de ARN?
- Cómo escribir un código para fusionar dos listas vinculadas ordenadas
- Cómo modificar Floyd Warshall para resolver Codeforces # 179 Div.1 B Greg y Graph
- ¿Qué tan valioso sería ser ubicado para aprender la estructura de datos usando C?
Entre las opciones que enumera, la única opción que importa es dividir y conquistar versus programación dinámica. En esencia, ambas son estrategias recursivas. En ambos casos, su trabajo es transformar la instancia dada del problema en una o más instancias más simples del mismo problema, que luego será resuelto por el Hada mágica de recursión. Por ejemplo:
* Búsqueda binaria: utilice una comparación para determinar si el valor objetivo es la mitad superior o la mitad inferior de la matriz ordenada, y luego deje que el Hada de recursión busque a través de la mitad correcta.
* Fusionar dos listas ordenadas: use una comparación para determinar el primer elemento en la lista de salida, y luego deje que el Hada de recursión combine el resto.
* Clasificación: deje que el Hada de la recursión clasifique la mitad superior y la mitad inferior de la matriz de entrada, y luego combine las dos mitades clasificadas (como se indicó anteriormente).
* Subsecuencia común más larga: hay tres opciones:
1. Descarta el primer personaje de A y deja que el Hada de la recursión encuentre la subsecuencia común más larga de lo que queda
2. Descarta el primer personaje de B, deja que el Hada de la recursión encuentre la subsecuencia común más larga de lo que queda
3. Acepte los primeros caracteres iguales de A y B como el primer carácter de la subsecuencia común más larga, y deje que el Hada de la Recursión descubra el resto.
Pruébelos todos e informe el mejor de esos tres resultados.
La principal diferencia entre las dos técnicas es que el enfoque de divide y vencerás produce subproblemas recursivos que son significativamente más pequeños (de n a n / 2 o n / 3 o 3n / 4, por ejemplo), mientras que el enfoque de programación dinámica produce recursivos subproblemas que son solo un poco más pequeños (típicamente de n a n-1 o n-2). Otra diferencia es que los algoritmos de divide y vencerás tienden a ser más sencillos (partición, recurrencia y limpieza), mientras que los algoritmos de programación dinámica (implícitamente) implican retroceso: intente esto, luego intente eso, luego intente lo otro y finalmente devuelva lo que sea El resultado fue el mejor.
El verdadero cuello de botella al aplicar cualquiera de estas estrategias es que hay que entender la recursividad . En particular, tienes que creer, realmente creer, que la recursión realmente funciona. Esas instancias más pequeñas son el problema de alguien más. Esas instancias más pequeñas no son asunto suyo. Si comienza a rastrear llamadas recursivas en lugar de confiar en que se resolverán correctamente, es muy probable que se pierda y se confunda. La hada de la recursión es tu amiga. Confía en el hada de la recursión. Si no.
