Divide y vencerás y programación dinámica

Esta página ofrece varios ejercicios corregidos sobre algoritmos, más específicamente comprendiendo la diferencia entre el paradigma Divide & Conquer (Divide y vencerás) y la programación dinámica. Los detalles de la búsqueda de ruta (camino más corto), problema de planificación, el problema del caudal máximo y, más en general, el Teoría de grafos se trata por separado.

Divide y vencerás y programación dinámica

Ejercicio 1

Escriba un pseudocódigo para un algoritmo de divide y vencerás para encontrar la posición del elemento más grande en una matriz de números. Escribe un pseudocódigo para un algoritmo de fuerza bruta, compara con el anterior. Mostrar un árbol del proceso del algoritmo divide y vencerás. ¿Cuál es el nivel máximo de árbol para los números?

divide y vencerás programación dinámica ejercicios corregidos

El algoritmo de fuerza bruta es trivial: un bucle.

En cada nivel l, el árbol binario completo se compone de 2^(l-1) hojas. Entonces el total de los vértices es 2^l -1. Sea l el nivel del árbol, entonces l=sup(log_2 (n)).

Ejercicio 2

Se le da una matriz con números enteros (positivo, negativo, cero) y se supone que debe encontrar la suma contigua máxima en esta matriz. Por lo tanto, necesita encontrar un subarreglo que dé la suma más grande. Ejemplo, si la matriz dada es: 5, -6, 7, 12, -3, 0, -11, -6

Suponga que su matriz de entrada se llama A. Lo que necesita hacer es formar otra matriz, digamos B, cada valor de i se calcula usando la fórmula recursiva, max(A[i], B[i- 1]+A[i ])

Lo que realmente haces es elegir expandir la ventana anterior o comenzar una nueva. Puede hacer esto ya que se supone que solo debe seleccionar elementos continuos como parte de sus subconjuntos.

5, -6, 7, 12, -3, 0, -11, -6

La respuesta sería 19 (del subarreglo {7,12} )

Ejercicio 3

Utilice la subcadena común más larga para: BDCABA y ABCBDAB. El algoritmo se describe de la siguiente manera:

divide y vencerás programación dinámica ejercicios corregidos subcadena común

Ejercicio 4

Haga coincidir la subcadena común más larga con la subsecuencia común más larga: BDCABA y ABCBDAB. El problema de la subsecuencia común más larga (LCS) es encontrar la subsecuencia común más larga de todas las secuencias en un conjunto de secuencias (a menudo solo dos secuencias).

Esto difiere de los problemas comunes de búsqueda de subcadenas: a diferencia de las subcadenas, no se requiere que las subsecuencias ocupen posiciones consecutivas en las secuencias originales.

Ejercicio 5

La distancia de Levenshtein es una métrica de cadena para medir la diferencia entre dos secuencias. De manera informal, la distancia de Levenshtein entre dos palabras es el número mínimo de modificaciones de un solo carácter (es decir, inserciones, eliminaciones o sustituciones) necesarias para cambiar una palabra por otra. Proponga un programa dinámico para resolver este problema. Ensayo con MEILENSTEIN y LEVENSHTEIN.

Ejercicio 6

Alice y Bob se turnan para jugar un juego, con Alice comenzando primero.

Inicialmente, hay un número n en el tablero. En el turno de cada jugador, ese jugador hace un movimiento que consiste en:

Elija cualquier x con 0 < x < n y n % x == 0.
Reemplace el número n en la pizarra con n – x.
Además, si un jugador no puede moverse, pierde el juego.

Devuelve true si y solo si Alice gana el juego, asumiendo que ambos jugadores están jugando de manera óptima.

Ejemplo 1:

Entrada: n = 2
Salida: verdadero
Explicación: Alice elige 1 y Bob no tiene más movimientos.

Ejemplo 2:

Entrada: n = 3
Salida: falso
Explicación: Alice elige 1, Bob elige 1 y Alice no tiene más movimientos.

Para responder a este problema, construiremos una tabla de soluciones. dp[i] indica el resultado del juego para el número i dado y para el jugador que comenzó el juego. Alice probará todos los factores y elegirá el que le dé a su oponente un valor perdedor.

juego divisor

También es posible resolver este problema de una manera recursiva más clásica, llamada Top-Down.

juego divisor

Y para un lado más práctico, vamos a agregar una memorización.

juego divisor

Ejercicio 7

Se le proporciona una matriz de costos de enteros donde costo[i] es el costo del i-ésimo escalón de una escalera. Una vez que haya pagado el costo, puede subir uno o dos escalones.

Puede comenzar desde el paso con el índice 0 o desde el paso con el índice 1.

Devolver el coste mínimo para llegar a la parte superior del piso.

Ejemplo 1:

Entrada: costo = [10,15,20]
Salida: 15

Explicación: Comenzará en el índice 1.
– Paga 15 y sube dos escalones para llegar a la cima.
El costo total es de 15.

Ejemplo 2:

Entrada: costo = [1,100,1,1,1,100,1,1,100,1]
Salida: 6

Explicación: Comenzará en el índice 0.
– Paga 1 y sube dos escalones para llegar a la pista 2.
– Paga 1 y sube dos escalones para llegar a la pista 4.
– Paga 1 y sube dos escalones para llegar a la pista 6.
– Paga 1 y sube un escalón para llegar a la pista 7.
– Paga 1 y sube dos escalones para llegar a la pista 9.
– Paga 1 y sube un escalón para llegar a la cima.
El costo total es de 6.

Para un primer borrador, resolveremos este problema recursivo. Para ello tenemos en cuenta el menor coste al considerar que retrocedemos un paso y dos pasos. Y así hasta tener el costo del primer o segundo paso.

costo mínimo (0) = costo [0]
costo mínimo (1) = costo [1]

mincost(i) = cost[i]+min(mincost(i-1), mincost(i-2))

Lo que da el siguiente código:

subiendo escaleras

En un segundo paso, nos mantendremos en un enfoque de arriba hacia abajo y agregaremos un sistema de memorización. Por lo tanto, un minCost ya encontrado no se volverá a calcular más tarde.

subiendo escaleras

Finalmente, tomaremos el problema de abajo hacia arriba para hacer programación dinámica;

subiendo escaleras

Ejercicio 8

Alice y Bob están jugando con montones de rocas. Hay un número par de pilas dispuestas en una fila, y cada pila tiene un número entero positivo de pilas de piedras[i].

El objetivo del juego es terminar con la mayor cantidad de piedras. El número total de piedras en todas las pilas es impar, por lo que no hay empate.

Alice y Bob se turnan, Alice comienza primero. Cada turno, un jugador toma toda la pila de piedras desde el principio o desde el final de la fila. Esto continúa hasta que no quedan más montones, momento en el que gana la persona con más piedras.

Suponiendo que Alice y Bob están jugando de manera óptima, devuelva true si Alice gana el juego o false si Bob gana.

Entrada: piedras = [5,3,4,5]
Salida: verdadero

Alice comienza primero y solo puede tomar los primeros 5 o los últimos 5.
Digamos que toma los primeros 5, por lo que la línea se convierte en [3, 4, 5].
Si Bob toma 3, entonces el tablero es [4, 5] y Alice toma 5 para ganar con 10 puntos.
Si Bob toma los últimos 5, entonces el tablero es [3, 4] y Alice toma 4 para ganar con 9 puntos.

Esto demostró que tomar el top 5 fue un movimiento ganador para Alice, por lo que devolvemos verdadero.

Comencemos con un enfoque de arriba hacia abajo con memorización.

  • Tenga en cuenta que ambos jugadores juegan de manera óptima, por lo que jugamos de manera óptima sin importar quién es Alice, quién es Bob.
  • Deje que dp (izquierda, derecha) devuelva [firstScore, secondScore] donde firstScore es la puntuación máxima cuando el jugador 1 juega primero, secondScore es la puntuación máxima cuando el jugador 2 juega segundo, recoge piedras en montones [left]... piles [right].
  • Para piedras en montones [izquierda]... montones [derecha], hay 2 opciones para que el jugador 1 elija:
    • Elija a la izquierda: pickLeft = dp (izquierda + 1, derecha).
      • Puntuación del jugador 1 = pilas [izquierda] + puntuación de segunda elección de pickLeft, por lo que firstScore = pilas [izquierda] + pickLeft [1]
      • Puntuación del jugador 2 = puntuación de la primera elección de pickLeft, por lo que secondScore = pickLeft[0]
    • Elegir a la derecha: elegirDerecha = dp(izquierda, derecha – 1).
      • Puntuación del jugador 1 = pilas [derecha] + segunda puntuación de pickRight, por lo que firstScore = pilas [derecha] + pickRight [1]
      • Puntuación del jugador 2 = puntuación de la primera elección de pickRight, por lo que secondScore = pickRight[0].
  • Necesitamos obtener la puntuación máxima cuando el jugador 1 juega primero entre más de 2 opciones.
  • Finalmente, dp(0, len(stacks) – 1) devuelve [firstScore, secondScore], donde alexScore = firstScore ya que Alice juega primero, leeScore = secondScore ya que Bob juega segundo.

juego de piedra

Ahora vamos a hacer un algoritmo de abajo hacia arriba mientras mantenemos la memorización. Así el algoritmo estará en programación dinámica.

juego de piedra

Ejercicio 9

Hay soldados haciendo fila. A cada soldado se le asigna un valor de rango único.

Debes formar un equipo de 3 soldados entre ellos según las siguientes reglas:

Elija 3 soldados con índice (i, j, k) con calificación (calificación [i], calificación [j], calificación [k]).
Un equipo es válido si: (puntuación[i] <puntuación[j] <puntuación[k]) o (puntuación[i] >puntuación[j] >puntuación[k]) donde (0 <= i < j < k < no).
Devuelve el número de equipos que puedes formar dadas las condiciones. (los soldados pueden formar parte de varios equipos).

Ejemplo 1:

Entrada: puntuación = [2,5,3,4,1]
Salida: 3
Explicación: Se pueden formar tres equipos dependiendo de las condiciones. (2,3,4), (5,4,1), (5,3,1).

Ejemplo 2:

Entrada: puntuación = [2,1,3]
Salida: 0
Explicación: No podemos formar ningún equipo dadas las condiciones.

Es fácil hacer un algoritmo codicioso. Este último está en O (n ^ 3), por lo que intentaremos mejorar el complejidad con programación dinámica.

programacion dinamica de equipo numero

Aquí está la idea principal en la versión de programación dinámica:

Primero, calculamos este caso score[i] > score[j] > score[k] dado que i > j > k. A continuación, calcule la puntuación del caso [i] < puntuación [j] < puntuación [k].

Establecer dp[i]: cuántos elementos en la notación de 0 a i-1 son menores que la notación[i].

Por cada vez que encontramos nota[i] > nota[j], acumulamos dp[j]. Aquí, dp[j] significa cuántas notas[k] existen desde 0 hasta j-1. Es decir, cuántos casos satisfacen grado[i] > grado[j] > grado[k].

programacion dinamica de equipo numero

Ejercicio 10

Se le proporciona un gráfico de precios donde el precio[i] es el precio de una acción dada en el i-ésimo día y una tarifa entera que representa las tarifas de transacción.

Encuentre la ganancia máxima que puede obtener. Puede realizar tantas transacciones como desee, pero debe pagar tarifas de transacción por cada transacción.

Nota: no puede participar en múltiples transacciones simultáneamente (es decir, debe vender las acciones antes de volver a comprar).

Entrada: precio = [1,3,2,8,4,9], tarifa = 2
Salida: 8

Explicación: La ganancia máxima se puede lograr mediante:
– Comprar a precios [0] = 1
– Vender a precios[3] = 8
– Comprar a precios [4] = 4
– Vender a precios[5] = 9

La ganancia total es ((8 – 1) – 2) + ((9 – 4) – 2) = 8.

Comencemos primero con el enfoque de arriba hacia abajo.

  • Sea dp(i, canBuy) la ganancia máxima que podemos obtener del precio[i..n-1] con el indicador canBuy == True significa que podemos comprar el i-ésimo día.
  • Para el iésimo día tenemos 2 opciones:
    • Ignóralo: beneficio = dp(i+1)
    • Cómpralo o véndelo
      • Si compra: beneficio = dp(i+1) – precio[i]
      • Si venta: beneficio = dp(i+1) + precio[i] – comisión

comprar vender programacion dinamica

Pasaremos a un enfoque de abajo hacia arriba para hacer una programación dinámica más tradicional.

Sea dp[i][j] el beneficio máximo que podemos obtener del precio[i..n-1] con bandera j == 1 significa que podemos comprar en el i-ésimo día.

comprar vender programacion dinamica

Dado que nuestro dp solo accede a 2 estados: el estado actual de dp dp, el estado anterior de dp dpPrev. Podemos optimizar a O(1) en complejidad espacial.

comprar vender programacion dinamica

Ejercicio 11

Planeaste un viaje en tren con un año de anticipación. Los días del año en los que viajará se dan como un número entero de días. Cada día es un número entero entre 1 y 365.

Los billetes de tren se venden de tres formas diferentes:

un pase de 1 día se vende al precio de [0] dólares,
un pase de 7 días se vende por un costo de [1] dólares, y
un pase de 30 días cuesta [2] dólares.
Los pases permiten tantos días de viaje consecutivos como sea posible.

Por ejemplo, si conseguimos un pase de 7 días el día 2, podemos viajar durante 7 días: 2, 3, 4, 5, 6, 7 y 8.
Devuelva la cantidad mínima de dólares que necesita para viajar cada día en la lista de días dada.
Entrada: días = [1,4,6,7,8,20], costos = [2,7,15]
Salida: 11

Por ejemplo, aquí tienes una forma de comprar pases que te permitan viajar de acuerdo a tu plan de viaje:
El día 1, compró un pase de 1 día por un costo[0] = 2 $, que cubría el día 1.
El día 3, compró un pase de 7 días por un costo[1] = 7 $, que cubría los días 3, 4, …, 9.
El día 20, compró un pase de un día por un costo[0] = 2 $, que cubría el día 20.

En total has gastado 11 $ y cubierto todos los días de tu viaje.

Veremos aquí el enfoque de abajo hacia arriba porque el razonamiento es muy similar al problema de mochila (mochila) en la construcción de la solución.

dp[i] significa hasta el día th el costo mínimo de los boletos. El tamaño de la matriz dp depende del último día de viaje, por lo que no necesitamos una longitud de matriz de 365.

Necesitamos una matriz booleana para marcar los días de viaje, la razón es que si no es un día de viaje, no necesitamos un boleto. Sin embargo, si es un día de viaje, consideramos tres escenarios (con tres tipos de boletos):

Si un billete de 1 día el día i, dp[i] = dp[i – 1] + coste[0]
Si un billete de 7 días finaliza el día i, dp[i] = min(dp[i – 7], dp[i – 6] … dp[i – 1]) + coste[1]
Si un billete de 30 días finaliza el día i, dp[i] = min(dp[i – 30], dp[i – 29] … dp[i – 1]) + coste[2]

Pero dado que el valor de la matriz dp aumenta, entonces:
Para un boleto de 7 días que finaliza el día i, dp[i] = dp[i – 7] + cost[1]
Para un boleto de 30 días que finaliza el día i, dp[i] = dp[i – 30] + cost[2]

boleto de programación dinámica

Ejercicio 12

Se le proporciona una matriz de valores enteros donde valores[i] representa el valor del i-ésimo sitio turístico. Dos sitios turísticos i y j tienen una distancia j – i entre ellos.

La puntuación de un par (i < j) de sitios turísticos es valores[i] + valores[j] + i – j: la suma de los valores de los sitios turísticos, menos la distancia entre ellos.

Devuelve la puntuación máxima de un par de miras.

Entrada: valores = [8,1,5,2,6]
Salida: 11

Tenemos i = 0, j = 2, valores[i] + valores[j] + i – j = 8 + 5 + 0 – 2 = 11

Supongamos que elegimos el sitio [i,…j]. La partitura se puede dividir en 2 partes.

La primera parte es el startGain que ganas al comenzar en un cierto punto i. Tenga en cuenta que startGain[i] = a[i] + i.

La segunda parte es endGain, que es la cantidad que ganas al terminar en cierto punto j. Tenga en cuenta que endGain[i] = a[j] – j.

Tenga en cuenta que endGain puede ser negativo.

La ganancia general para [i,…j] no es más que startGain[i] + endGain[j]. (Esto puede ser fácilmente verificado por las definiciones).

Debemos maximizar la ganancia total.

¿Cuáles son las posiciones posibles para iniciar el viaje? Está claro que podemos empezar todo menos el último elemento. Por lo tanto, el viaje óptimo debe comenzar en uno de estos elementos.

Supongamos que solo se nos permite iniciar un viaje en i. ¿Cuál es la cantidad máxima que podemos ganar en este caso? Bueno, dado que startGain es fijo, necesitamos maximizar endGain. Podemos hacer esto deteniéndonos en un elemento que tenga la ganancia final máxima siempre que aparezca a la derecha de i.

Como se muestra arriba, para cada i necesitamos encontrar la ganancia final máxima a su derecha.

maxEndRight[i] = max(maxEndRight[i+1], endGain[i+1]) = max(maxEndRight[i+1], a[i+1] – (i+1))

maxEndRight[i] representa la ganancia final más alta que puede obtener deteniéndose en cualquier punto estrictamente a la derecha de i. Como por definición ya conocemos endGain[i+1] (la mayor ganancia posible al terminar en cualquier punto a la derecha de i+1), solo tenemos que comprobar la posibilidad de saber si s detenerse en i+1 sería beneficioso O no. De ahí la definición de DP.

Para cada i válida, gananciageneral[i] = gananciainicial[i] + maxEndRight[i] = a[i] + i + maxEndRight[i]

Tenga en cuenta que maxEndRight[i] solo depende de maxEndRight[i+1]. Por lo tanto, podemos usar 2 variables para rastrear valores anteriores.

Dado que necesitamos el valor de maxEndRight[i+1] para calcular el valor de maxEndRight[i], comenzamos las iteraciones desde atrás.

Como se indicó, los viajes no pueden comenzar en el último elemento, por lo que el ciclo for comienza en i=n-2. Para este valor, maxEndingRight se inicializa en endGain[lastIndex] porque esa es la única forma posible de finalizar el viaje.

exploración de programación dinámica

Compartir, repartir
es_ESES