No existe una forma tan fácil de resolver un problema de DP. La programación dinámica se puede dominar solo a través de la práctica. Después de practicar algunos problemas, comenzará a ver patrones. Oh … Necesitamos tomar una matriz 2D y llenarla en diagonal. ¿Por qué no tomamos una matriz 1D y ahorramos espacio?
Practique los problemas de DP con los siguientes recursos:
Archivos de programación dinámica – GeeksforGeeks
Resuelva las siguientes preguntas para comprender un concepto sólido sobre DP:
1. Valor máximo de la subsecuencia contigua. Dada una secuencia de n números reales A1. . .An, determine una subsecuencia contigua Ai. . .Aj para el cual la suma de elementos en la subsecuencia se maximiza.
2. Realizar cambios: se le dan n tipos de denominaciones de monedas de valores v1 <v2 <. . . <vn (todos los enteros). Suponga que v1 = 1, para que siempre pueda hacer cambios por cualquier cantidad de dinero C. Dé un algoritmo que haga el cambio por una cantidad de dinero C con la menor cantidad de monedas posible.
- ¿Por qué diferenciamos entre máquinas Turing universales y máquinas Turing normales?
- Cómo derivar el mecanismo de conversión de convertir decimal a binario y viceversa
- ¿Dónde puedo obtener un código para la entrada y salida rápida de enteros, enteros largos largos, flotante, doble, caracteres y cadenas para C?
- ¿Cuál sería la relación más efectiva entre las matemáticas y la programación en educación?
- ¿Por qué las matemáticas son importantes para la inteligencia artificial y el aprendizaje automático?
3. Subsecuencia creciente más larga: Dada una secuencia de n números reales A1. . .An, determine una subsecuencia (no necesariamente contigua) de longitud máxima en la que los valores en la subsecuencia forman una secuencia estrictamente creciente.
4. Apilamiento de cajas : se le da un conjunto de n tipos de cajas rectangulares tridimensionales, donde la caja i-ésima tiene altura hi, ancho wi y profundidad di (todos los números reales). Desea crear una pila de cajas que sea lo más alta posible, pero solo puede apilar una caja encima de otra caja si las dimensiones de la base 2-D de la caja inferior son estrictamente más grandes que las de la 2- D base de la caja superior. Por supuesto, puede girar una caja para que cualquier lado funcione como su base. También está permitido usar múltiples instancias del mismo tipo de cuadro.
5. Construcción de puentes: considere un mapa en 2-D con un río horizontal que pase por su centro. Hay n ciudades en la orilla sur con coordenadas x a1. . . ciudades an y n en el banco norte con coordenadas x b1. . . bn. Desea conectar tantos pares de ciudades norte-sur como sea posible con puentes de modo que no se crucen dos puentes. Al conectar ciudades, solo se le permite conectar la i-ésima ciudad en el banco norte con la i-ésima ciudad en el banco sur.
6. Problema de mochila entera (artículos duplicados prohibidos): este es el mismo problema que el ejemplo anterior, excepto que aquí está prohibido usar más de una instancia de cada tipo de artículo.
7. Partición equilibrada: tiene un conjunto de n enteros cada uno en el rango 0. . .K. Particione estos enteros en dos subconjuntos de modo que minimice | S1 −S2 |, donde S1 y S2 denotan las sumas de los elementos en cada
1 de los dos subconjuntos.
8. Editar distancia: Dadas dos cadenas de texto A de longitud n y B de longitud m, desea transformar A en B con un número mínimo de operaciones de los siguientes tipos: eliminar un carácter de A, insertar un carácter en A o cambia un personaje en A por un personaje nuevo. El número mínimo de tales operaciones requeridas para transformar A en B se llama la distancia de edición entre A y B.
9. Contando paréntesis booleanos: se le da una expresión booleana que consiste en una cadena de los símbolos ‘verdadero’, ‘falso’, ‘y’, ‘o’, y ‘xor’. Cuente la cantidad de formas de paréntesis de la expresión
tal que se evaluará como verdadero. Por ejemplo, solo hay 1 forma de paréntesis ‘verdadero y falso xo verdadero’ de modo que se evalúe como verdadero.
10. Estrategia óptima para un juego: considere una fila de n monedas de valores v1. . . vn, donde n es par. Jugamos un juego contra un oponente alternando turnos. En cada turno, un jugador selecciona la primera o la última moneda de la fila, la retira de la fila de forma permanente y recibe el valor de la moneda. Determine la cantidad máxima posible de dinero que definitivamente podemos ganar si nos movemos primero.
11. Recorrido en dos personas de una secuencia de ciudades: se le da una secuencia ordenada de n ciudades y las distancias entre cada par de ciudades. Debe dividir las ciudades en dos subsecuencias (no necesariamente contiguas) de modo que la persona A visite todas las ciudades en la primera subsecuencia (en orden), la persona B visite todas las ciudades en la segunda subsecuencia (en orden), y tal que la suma de las distancias totales recorridas por A y B se minimizan. Suponga que la persona A y la persona B comienzan inicialmente en la primera ciudad en sus subsecuencias respectivas.
12. Empaquetado de contenedores (versión simplificada): tiene n1 elementos de tamaño s1, n2 elementos de tamaño s2 y n3 elementos de tamaño s3. Desea empaquetar todos estos elementos en contenedores de capacidad C, de modo que se minimice el número total de contenedores utilizados.
