Objetivo de dynamic programming: evitar calcular lo mismo varias veces, manteniendo una tabla de los resultados a medida que se calculan, para luego usarlos en la solución de las subinstancias
Divide and conquer es una familia con un sistema top-down, porque vamos de la instancia completa, hasta llegar a subinstancias.
Por otro lado, Dynamic Programming, es bottom-up, se inicia con las subinstancias mas pequeñas y simples, y combinando sus soluciones obtenemos la respuestas de otras mas grandes, hasta dar con la solución final.
1. Describir estructura:
2. Definir el valor
3. Calcular el valor
4. Calcular solución (opcional)
memoización: para top-down, recursivos:
tabulacion para bottom-up, iterativos:
Se utiliza el triángulo de Pascal, como tabla de valores intermedios. No es necesaria toda la tabla: es suficiente con un vector de tamaño k, que es una línea, luego se actualiza el vector de izquierda a derecha.
Coeficiente binomial:
->El problema de coeficiente binomial (n/k) es: tiempo a en 8(n k) y espacio 8(k).
The World Series:
A= p y B =q=1-p.
P(i,j) probabilidad de que el equipo A gane, cuando le faltan i ganes, y a B le faltan j ganes.
P(i,j) = pP(i-1,j)+qP(i,j-1)
->El problema de la serie mundial es t(k) donde k=i+j, O(2^k). O(4^n) si j=i=n.
En términos de coeficiente binomial:
C(i+j,j) = C(i+j-1, j) + C(i+j-1, j-1)
-> Con triangulo de Pascal se puede hacer 8(n^2)
Cambio:
Se hace una tabla donde las filas son las denominaciones disponibles, y las columnas son de 0 a N, valor a pagar. c[i, j] menor numero de monedas para pagar j, con monedas de 1 a i.
Se calcula c[i,0] y después de eso, se puede calcular de derecha a izquierda columna por columna, o de arriba a abajo fila por fila.
c[i, j] = min(c[i-1, j],1+c[i, j-di])
-> 8(n+c[n,N])
Principio de la optimalidad:
en una secuencia optima de decisiones o selecciones, cada subsequencia también debe ser óptima.
O sea, si necesito un resultado optimo, todos los pequeños resultados en el camino(la tabla) deben ser óptimos.
Cuando el principio no aplica, entonces probablemente no se puede usar prog dinámica.
Un problema para el principio es los recursos, puedo agotar los recursos en una subinstancia del problema.
La solución óptima a cualquier instancia no trivial de un problema, es la combinación de optimas soluciones de algunas de sus subinstancias.
Problema de la mochila:
vi y wi son restricciones de la instancia. Y xi (es 1 o 0 si está o no está en la mochila) son restricciones de la solución.
Se hace una tabla, con filas para cada objeto y columnas para su peso. Por eso V[i,j] es la cantidad de objetos que podemos llevar en la mochila de peso j. Con objetos de 1 a i.
v[i,j] = max(V[i-1, j],V[i-1,j-wi]+vi)
-> construir la tabla 8(nW) y la composision se determina en tiempo o(n+W)
Camino más corto:
Dk[i,j] = min(Dk[i,j],Dk-1[i,k]+Dk-1[k,j])
No entendí
Multiplicación matricial en cadena:
La complejidad de una multiplicación de matrices: es pqr. La idea es encontrar la mejor forma de poner paréntesis para que sean menos multiplicaciones.
Supongamos hago un corte de m1 a mi= M= (m1,m2,m3,...mi)(mi+1,mi+2,...mn) ambas deben ser optimas(principio de la optimabilidad).
Recurrencia T(n)= Suma de i=1 hasta n-1 de T(i)T(n-i). Sus valores son llamados números catalanes. -> omega(4^n/n)
-> alg con diagonal, n^3
Ejemplos con recursión:
-Matrices:
Se puede hacer calculando M con una función fm() que sea recursiva. Para saber cuantas multiplicaciones se ocupan se llama a fm(1,n)
-> Toma Omega(2^n), O(3^n)
Funciones de memoria:
Combinar las ventajas de top down y de bottom up. Se hace con una función de memora.
Se tiene la tabla de valores, si ya esa tabla se calculó se retorna el valor correspondiente. Si no, se llama recursivamente a la función.
-> tiempo: 8(nk) y espacio omega(nk)