© TippaPatt/Shutterstock.com
La programación dinámica (DP) es un área exigente de la programación informática, con habilidades y técnicas específicas para resolver problemas. Sí, te las arreglarás como ingeniero de software sin él, pero la programación dinámica tiene importantes aplicaciones del mundo real y es posible que te pregunten sobre ella en una entrevista con un desarrollador.
Si eres nuevo en el mundo dinámico programación o desea actualizar sus habilidades, este breve artículo explica qué es la programación dinámica, con ejemplos y dónde puede desarrollar sus habilidades de DP en línea.
¿Qué es la programación dinámica?
En la programación informática, la programación dinámica (DP) es un método de resolución de problemas que estructura y simplifica problemas complicados dividiéndolos en una cascada de subproblemas superpuestos. Al aplicar DP, se pueden resolver de manera eficiente múltiples clases de problemas.
DP tiene su origen en las matemáticas y es aplicable en diversos campos, desde la bioinformática hasta la ingeniería de recursos hídricos y la economía.
¿Cómo funciona la Programación Dinámica en informática?
La programación dinámica tiene que ser aplicada apropiadamente para ser utilizada en la programación de computadoras. Un problema debe tener dos características para ser adecuado para DP:
Una subestructura óptima: Un problema específico tiene una propiedad de subestructura óptima si su solución óptima puede derivarse de las soluciones óptimas de sus subproblemas. Subproblemas superpuestos: el problema en cuestión debe poder dividirse en una cascada de subproblemas reutilizables o un algoritmo recursivo que pueda resolver subproblemas repetidamente sin generar otros nuevos.
Estas dos propiedades son clave para usar DP. Si la solución óptima se encuentra utilizando subproblemas que no se superponen, no se puede utilizar DP. En su lugar, se usa divide y vencerás. Del mismo modo, los algoritmos de clasificación como clasificación por fusión y clasificación rápida no son DP.
Recursión y programación dinámica
La recursión es una clave propiedad de las subestructuras óptimas utilizadas en DP. La recursividad es simplemente un proceso que se repite, como cuando te paras entre dos espejos y tu reflejo se repite una y otra vez (el efecto Droste).
Las subestructuras óptimas tienen cascadas de problemas que se resuelven continuamente y el problema principal recursivamente.
Un algoritmo recursivo en DP no genera nuevos subproblemas, manteniendo la cantidad de espacio tomado por los subproblemas superpuestos individuales pequeños. Idealmente, los mismos subproblemas deberían resolverse una y otra vez.
¿Tipos clave de programación dinámica?
Hay dos tipos o métodos de DP que dependen de cómo enfoque un problema. Ambos métodos utilizan soluciones de memorización, almacenamiento y tabulación para que puedan recuperarse rápidamente, ahorrando el tiempo de repetir el cálculo.
De arriba hacia abajo
En el enfoque de arriba hacia abajo, la solución a un problema es recursiva, lo que permite la memorización de soluciones a los subproblemas superpuestos. Los nuevos subproblemas subsiguientes se resuelven consultando la caché de datos memorizados para ver si ya existe una solución. Si el subproblema no ha sido resuelto previamente, éste y su solución se añaden a la memoria caché.
La DP de arriba hacia abajo es fácil de entender y usar, ya que facilita la resolución específica de subproblemas. Puede depurarlo fácilmente, pero este enfoque recursivo puede consumir una gran cantidad de memoria caché, lo que puede provocar errores de desbordamiento de pila.
De abajo hacia arriba
El enfoque de abajo hacia arriba, también conocido como tabulación o llenado de tablas, utiliza la tabulación para crear un registro de subproblemas y soluciones almacenados. Luego utiliza los subproblemas resueltos tabulados para una reformulación ascendente del problema. Los subproblemas más pequeños se resuelven y las soluciones se aprovechan para resolver subproblemas más grandes. El bucle For se puede utilizar para iterar los subproblemas.
Ejemplo: programación dinámica y la serie Fibonacci
Un ejemplo práctico de programación dinámica en acción que trabaja con la serie Fibonacci:
0, 1, 1, 2 , 3, 5, 8, 13, 21, 34, 55…
Con los números de Fibonacci (Fn), cualquier número de la secuencia es la suma de los dos números anteriores. A medida que aumenta el valor de’n’en Fn, aumentan la escala y la complejidad del cálculo de estos números.
DP se puede utilizar para calcular cualquier número de Fibonacci. Al usar DP, no tiene que generar un árbol recursivo o resolver problemas una y otra vez. Simplemente use los valores calculados previamente. Así es como el código busca una implementación de esta serie usando el método de arriba hacia abajo:
El código para calcular cualquier número de Fibonacci.
©”TNGD”.com
¿Por qué es importante la programación dinámica?
La programación dinámica no es una parte destacada del panorama de la programación moderna. Esto se debe a que generalmente no se usa directamente en el desarrollo a nivel de producción contemporáneo.
Muchos ingenieros competentes se han establecido sin tener más que un conocimiento mínimo de DP, a pesar de ser parte de lenguajes de programación líderes como:
PythonJavaScriptRubyPHPPerlLua
El conocimiento práctico de DP es valioso para los ingenieros porque puede ayudar a los desarrolladores a crear aplicaciones de software mejor estructuradas y más eficientes.
La arquitectura moderna de servicios compartidos consiste en aplicaciones independientes que acceden a los recursos (memoria, potencia de procesamiento, capacidad de red, costos) de un grupo compartido. El código mal estructurado con poca atención a la resolución de problemas puede conducir al consumo innecesario de recursos, lo que afecta el rendimiento de otras aplicaciones. DP ayuda a refinar el código de software para evitar que esto suceda.
Ejemplos del mundo real de programación dinámica
Hay muchos ejemplos de aplicaciones de software del mundo real que usan DP para mantenerse ágiles y eficientes y minimizar los requisitos del sistema para ejecutarlas. Estos son algunos ejemplos:
Google Maps: en Google Maps, DP se usa para identificar la ruta más corta entre un único punto de partida y una variedad de destinos. Motores de búsqueda: para calcular el grado de similitud entre dos piezas de contenido en línea.Software antiplagio: Desarrollo de un algoritmo de distancia de documentos para ayudar a detectar el nivel de similitud entre documentos de texto. Redes: Transferencia de datos de una sola fuente a varios receptores diferentes secuencialmente. Correctores ortográficos: El algoritmo de distancia de edición que se utiliza para cuantificar cuán diferentes son dos son las palabras y calcular el número de operaciones necesarias para convertir una palabra en otra.
Bases de datos/caché de base de conocimiento: almacenamiento de consultas/solicitudes comunes en memoria local accesible o cachés. DP ayuda a evitar la obtención repetida de datos de uso común de los servidores, a favor del almacenamiento local.
Ejemplos de preguntas de entrevista de programación dinámica
Si está buscando su próximo trabajo como ingeniero de software o desarrollador, el conocimiento de DP le dará la ventaja en las entrevistas de trabajo.
DP es una gran cosa en las entrevistas de tecnología. ¡Empresas tecnológicas líderes como Google y Amazon desafían a los candidatos con preguntas de DP que deben resolverse en el acto! Esto es para probar cómo piensan los desarrolladores, y si desglosarán las tareas y encontrarán las formas más eficientes en recursos para resolver problemas.
Aquí hay algunos ejemplos de preguntas y respuestas de entrevistas de programación dinámica
Además de la ecuación de Fibonacci que se muestra arriba, aquí hay algunas preguntas comunes de entrevistas de programación dinámica, con ejemplos de respuestas y soluciones:
Pregunta 1: ¿Puede explicar las ventajas y desventajas de Memoización?
(Sugerencia: esta es una pregunta sobre los pros y los contras del enfoque de arriba hacia abajo en DP)
Respuesta:
Las ventajas de la memorización incluyen:
la codificación es fácil Se puede abordar un problema escribiendo un contenedor o una anotación que ejecutará automáticamente la función recursiva Las respuestas se pueden obtener de un caché y se pueden usar para múltiples problemas
de cálculos, puede quedarse rápidamente sin espacio en la pila.
Pregunta 2: Está subiendo aires Puedes subir uno o dos escalones a la vez. ¿De cuántas maneras diferentes hay para subir a la cima?
(Pista: esta pregunta se conoce como el problema de’subir escaleras’)
Respuesta: Observa el enfoque para esta pregunta común de la entrevista de codificación en este video:
¿Dónde puedo practicar la programación dinámica?
Desarrollar habilidades en programación dinámica fortalece las habilidades de pensamiento y resolución de problemas de los desarrolladores. DP también puede ayudarlo a pensar de manera más integral sobre los problemas y desarrollar soluciones inusuales pero efectivas. Si es hora de que obtenga capacitación o certificaciones en DP, aquí hay 3 de los mejores cursos en línea:
Una vez que esté al día, ¡la práctica hace al maestro!
Redondeando arriba
La programación dinámica puede no ser parte de su paquete de desarrolladores, pero es importante para las corporaciones para las que desea trabajar. ¡Comprender y aprender DP no solo le permitirá obtener trabajos, sino que también refinará sus habilidades y lo ayudará a escribir el código limpio que le encantará a su desarrollador principal!
¿Qué es la programación dinámica, con ejemplos? Preguntas frecuentes (FAQ)
¿Qué es la memoización?
En programación, la memoización es una técnica de optimización que almacena los resultados de funciones con muchos recursos en un caché para que puedan ser llamadas rápidamente si se requieren de nuevo. Esto aumenta la velocidad y la eficiencia de los programas informáticos.
¿Qué es la tabulación?
La tabulación es otro término para el enfoque ascendente de la programación dinámica. Se llena una tabla con las soluciones de los subproblemas más bajos y se usa para calcular la respuesta a los subproblemas en los niveles más altos hasta que se encuentra la solución original.
¿Qué es divide y vencerás?
Divide y vencerás es otra técnica para resolver problemas. Toma el problema original y lo divide en subproblemas relacionados más pequeños que se pueden resolver de forma independiente.
¿Es difícil la entrevista de codificación de Google?
Sí. Esta entrevista virtual tiene la reputación de ser una de las más duras del sector tecnológico. Las preguntas requieren una amplia investigación y práctica y, por lo general, cubren temas relacionados con los servicios de Google. A menudo se hacen preguntas de DP.
¿Amazon pregunta a los candidatos de entrevistas de ingeniería de software acerca de la programación dinámica?
Sí. Amazon no duda en hacer preguntas de programación dinámica avanzada a los candidatos para separar a los que no están preparados.