No hay nada especial en la programación dinámica 3D.
¿Entiendes el concepto de programación dinámica? Si lo entiende, debería ser capaz de entender la programación dinámica 1D, 2D, 3D, 4D … No importa, cómo-cuántos-muchos-D . Porque no hay diferencia en absoluto.
La programación dinámica consiste en evitar resolver los mismos problemas una y otra vez. Tienes una gráfica de estados, estás resolviendo algo usando esa gráfica. Eso es todo. Ha dirigido un gráfico acíclico, está procesando los vértices de este gráfico en orden de su clasificación topológica. De arriba a abajo y de abajo a arriba son solo formas diferentes de proceder a una gráfica dada. ¿La gráfica tiene algunas “dimensiones”? A veces, el gráfico tiene una estructura específica y es más fácil representarlo como una cadena (1D dp) o una cuadrícula (2D dp), a veces puede ser un hipercubo (DP con máscaras de bits) . A veces es difícil elegir una buena representación. Cuando está codificando un estado con máscara de bits, ¿es 1D DP o DP no-dimensional? Puede pensar en ello como 1D, porque su estado es un número único; al mismo tiempo, puede pensar que se trata de DP n-dimensional, ya que cada bit de su número representa un parámetro separado. Simplemente puede enumerar todos los estados de su DP y se convertirá en 1D.
Digamos que está resolviendo algún tipo de problema de mochila, tratando de comprar los mejores artículos por una cantidad determinada de dinero, y el subproblema es cuántos centavos tiene ahora. Es 1D, ¿verdad? ¿Y qué hay del subproblema “cuántos dólares y cuántos centavos tienes” ? Es 2D, ¿verdad? Pero el problema es el mismo. Y los estados son iguales: solo los enumeró de una manera diferente, agregando una dimensión más. Para algunos problemas es más natural verlos como 2D o 3D, para algunas otras tareas, 1D se adapta mejor. Pero no se trata de tener clases de problemas completamente diferentes aquí.
- ¿Cuáles son los mejores recursos para aprender sobre el aprendizaje profundo?
- ¿Cuáles son algunos de los mejores libros sobre informática?
- ¿Cuáles son algunos buenos recursos gratuitos para dominar las escalas de blues para el saxofón alto?
- ¿Dónde puedo aprender Array, estructura y punteros desde el nivel básico hasta el avanzado (lenguaje C)? yo
- ¿Cómo se puede aprender Hadoop, Pig, Hive, Cassandra y MongoDB? ¿Cuáles son los mejores recursos?
Si está familiarizado con el DP en general, 3D DP debe ser fácil de manejar; si aún no entiende la DP, comience con los conceptos básicos de la DP; no se centre en la cantidad de dimensiones, ese no es el criterio principal para describir el algoritmo DP o medir su dificultad.
Puede consultar esta pregunta: ¿Existen buenos recursos o tutoriales para la programación dinámica (DP), además del tutorial de TopCoder? Contiene muchas buenas respuestas y enlaces útiles para el aprendizaje de la DP en general.