La programación dinámica se trata de usar las soluciones de subproblemas para resolver el problema real. Por lo tanto, encontrar series de Fibonacci con memorización es una programación dinámica, también lo es encontrar la suma de prefijos y muchas otras simples.
La mayoría de los DP son intuitivos con suficiente experiencia (aunque no todos). Pero el punto sigue siendo cómo usar la respuesta formulada en función de las soluciones de los subproblemas. Como su pregunta, enumeraré algunos DP clásicos que debe conocer, muchos de los problemas de DP están inspirados en
- Encontrar la distancia mínima de edición
- Encontrar el palíndromo más largo
- Multiplicación de cadena matricial
- Problema de vendedor ambulante (recorriendo todas las ciudades)
- Subarray de suma más grande
- Subcadena y subsecuencia común más largas
- Suma máxima que aumenta subsecuencia
- Floyd Warshall
- Cambio de moneda
- Partición casi igual (matriz de partición en 2 subconjuntos de modo que la diferencia de suma sea mínima)
- Problema de suma de subconjuntos (si puede resolver esto, el problema anterior de la partición igual se resolverá automáticamente)
- Juegos simples de MaxMin
Una vez que profundice, todos los problemas parecerán interrelacionados porque realmente lo están. 🙂
- ¿Cuáles son las principales diferencias, con ejemplos, entre un algoritmo de aprendizaje profundo y un algoritmo de aprendizaje de refuerzo?
- Digamos que encontramos un algoritmo que resuelve problemas de NP-Complete en tiempo polinómico pero no podemos probarlo. ¿Cuáles serían las consecuencias?
- Cómo comparar dos algoritmos de recomendación en términos de problema de cola larga
- Cómo explorar los datos para elegir un algoritmo de aprendizaje automático
- ¿Podría un algoritmo informático convertirse en el presidente de los Estados Unidos?
A partir de ahora, no puedo pensar en más problemas clásicos de DP. Espero eso ayude.
