¿Cuáles son las mejores fuentes para practicar problemas de programación dinámica?

http://Www.hackerrank.com
http://Www.topcoder.com
http://Www.codechef.com
Hackerrank tiene una sección adecuada relacionada con la programación dinámica.
Para topcoder y codechef puede buscar en sus archivos con la etiqueta “dinámico” o “dp”, estoy seguro de que obtendrá las preguntas que está buscando.

Actualizar:
Encontré este sitio Concursos virtuales en línea que tiene una lista realmente grande de problemas de DP categorizados según un nivel. Es toda una colección de problemas de DP de otros sitios.

PD: sugiera otros enlaces para actualizar con

Libro de programación competitiva segunda edición (ahora tercera), Steven y Felix Halim!

Allí encontrará muchos problemas del juez en línea de UVA relacionados con DP.

¡Deberías echar un vistazo allí! 😉

Puede consultar Techie Delight para problemas interesantes de DP y sus soluciones. Incluso han dividido los problemas de DP en archivos de Tabulación (Enfoque ascendente) y Memoización (Enfoque descendente).

Aquí está la lista completa:

1. Introducción a la programación dinámica
2. Subsecuencia común más larga | Introducción y longitud de LCS
3. Subsecuencia común más larga | Versión optimizada para espacio
4. Subsecuencia común más larga de secuencias K
5. Subsecuencia común más larga | Encontrar todos los LCS
6. El problema de subcadena común más largo
7. La subsecuencia palindrómica más larga usando programación dinámica
8. Problema de subsecuencia repetida más larga
9. Implementar la utilidad Diff
10. Supersecuencia común más corta | Introducción y longitud SCS
11. Supersecuencia común más corta | Encontrar todos los SCS
12. Supersecuencia común más corta | Usando LCS
13. Subsecuencia creciente más larga usando programación dinámica
14. Subsecuencia bitónica más larga
15. Subsecuencia creciente con suma máxima
16. El problema de la distancia de Levenshtein (Editar distancia)
17. Encuentre el tamaño de la submatriz cuadrada más grande de 1 presente en una matriz binaria dada
18. Multiplicación de cadena matricial
19. Encuentre el costo mínimo para llegar a la última celda de la matriz desde su primera celda
20. Encuentra la secuencia más larga formada por números adyacentes en la matriz
21. Cuente el número de rutas en una matriz con un costo dado para llegar a la celda de destino
22. 0-1 problema de mochila
23. Maximiza el valor de la expresión
24. Problema de partición
25. Problema de suma de subconjunto
26. Problema de partición de suma mínima
27. Encuentra todas las cadenas binarias de N dígitos sin ningún 1 consecutivo
28. Corte de varilla
29. Máximo corte de varilla de producto
30. Problema de cambio de monedas (suministro ilimitado de monedas)
31. Problema de cambio de moneda: encuentre el número total de formas de obtener la denominación de monedas
32. La subsecuencia alterna más larga
33. Cuente el número de veces que aparece un patrón en una cadena dada como una subsecuencia
34. Recoge los puntos máximos en una matriz satisfaciendo las restricciones dadas
35. Cuente el total de combinaciones posibles de números de N dígitos en un teclado móvil
36. Encuentre el costo óptimo para construir un árbol de búsqueda binario
37. Word Break Problem
38. Coincidencia de patrones comodín
39. Encuentre la probabilidad de que una persona esté viva después de dar N pasos en la isla
40. Calcular la suma de todos los elementos en una submatriz en tiempo constante
41. Encontrar la suma máxima de la submatriz K x K en una matriz M x N dada
42. Encuentra la submatriz de suma máxima presente en una matriz dada
43. Encuentra la suma máxima de subsecuencia sin elementos adyacentes
44. Problema de submatriz máxima (algoritmo de Kadane)
45. Senderos más cortos de una sola fuente: algoritmo Bellman Ford
46. Caminos más cortos de todos los pares – Algoritmo de Floyd Warshall

La programación dinámica requiere buenos conocimientos básicos sobre los casos básicos para relacionarlo con el problema que está resolviendo.

Antes de llegar a la fase de resolución de problemas, comprenda los conceptos a fondo, uno debe referirse a las fuentes como la serie de conferencias de programación dinámica del MIT, la serie de conferencias de programación dinámica Saurabhschool.

Una vez hecho esto, el mejor recurso para obtener un buen control sobre DP es practicar los problemas de Hackerrank y GeeksForGeek

Tuve que escribir los sistemas de ecuaciones para estos problemas en la tarea y en las pruebas. Terminé las pruebas de 2 horas en 15 minutos y salí de la habitación.

Mi especialidad fue SSM (Sistemas de Ciencias y Matemáticas) en la Universidad de Washington en St. Louis, 1972-1975, y el trabajo que hice, mis profesores escribieron los documentos y obtuvieron el crédito por ello. No me importó y todavía no.

La mejor información que tengo es que una supercomputadora Karmarkar (Narendra Karmarkar) es la mejor plataforma para esto ahora.

Aunque está destinado a resolver problemas de programación lineal en tiempo polinómico, su mal uso causó el viernes 13 el mini accidente en 1989, que yo sepa.

Realmente no sé qué es la programación dinámica.

Más de 50 problemas de programación dinámica y su implementación por Dheeraj Kuamar en GeeksforGeeks

https://uva.onlinejudge.org/inde …

Aquí encontrará algunos problemas DP importantes e interesantes. Estos problemas son apropiados para comenzar a aprender DP.

Puedes comenzar con Hackerrank:
HackerRank
Contiene una sección bien organizada con un nivel de dificultad creciente.

TopCoder es probablemente con los mejores problemas.
Eche un vistazo a SPOJ o Timus Online Judge.