Mirando la mayoría de los problemas de DP, ¡no parecen ser solucionables usando DP en el primer sitio! Si intentas resolverlo pensando que es un problema de DP, lo más probable es que no lo entiendas.
En cambio, olvídate de DP, ¡aplica la fuerza bruta primero! Entonces, lo más probable es que caigas en la recursión. Felicidades, el trabajo está casi terminado 😀 Ahora, solo mira, ¿si estás haciendo un trabajo repetitivo? ¿Puedes usar alguna matriz o tabla para almacenar el valor de las llamadas de recursión para usarlo más tarde? ¿Cuántos parámetros hay en la llamada de recursión y puede hacer la memorización ahora de acuerdo con el número de parámetros? Lo más probable es que ahora obtenga el problema y lo resuelva 🙂
Ahora, veamos cómo debemos comenzar, si no sabemos nada sobre DP 🙂
- Silicon Valley (serie de televisión): ¿Cuál es el ejemplo más cercano en la vida real al algoritmo de compresión de Pied Piper?
- Cómo crear mi propia función de hash para usar en una tabla de búsqueda
- Cómo escribir un código para fusionar dos listas vinculadas ordenadas
- ¿Cuál es el algoritmo utilizado para la agrupación de documentos de texto después de aplicar LSA?
- ¿Cómo funciona el 'algoritmo tabula rasa' de AlphaGo Zero?
- Primera y más importante parte, toma ese libro CLRS. Abra su capítulo de programación dinámica, léalo completo y entiéndalo completamente. En él se dan tres problemas básicos de DP: corte de varilla, multiplicación de cadena de matriz y LCS. Comprenda completamente cómo nos hemos acercado a su solución, por qué esta solución funciona, etc., todo.
- Ahora, cuando conozca los conceptos básicos de DP, vaya a Algorithms GeeksforGeeks y vea todos los problemas aquí. Estos son todos los problemas de DP más comunes y casi todos los problemas que enfrentará, sería solo la variación de estos problemas.
- Ahora, ya ha terminado de recoger todas sus armas, es hora de la guerra 😀 Intente resolver tantos problemas como pueda en jueces en línea como spoj, codechef, hackerearth, hackerrank, etc. Puede encontrar un buen comienzo aquí Juez en línea A2. Intenta resolver desde los más fáciles hasta los más difíciles.
- Primero intente su mejor nivel para resolver un problema en particular. No se desanime si no puede resolver ningún problema. Después de hacer todo lo posible, busque su solución en Internet, discuta con sus compañeros, trate de ver cómo se aborda el problema, por qué y cómo su pensamiento era incorrecto, cómo se resolvió, etc. Esta es la única manera de mejorar programación competitiva 🙂
- Repita los pasos 3 y 4 😀
Todo lo mejor 🙂
