Diferencia entre Divide y Conquer Algo y Programación Dinámica

Divide and Conquer

Divide and Conquer funciona dividiendo el problema en subproblemas, conquistando cada subproblema de forma recursiva y combinando estas soluciones.

Programación Dinámica

La Programación Dinámica es una técnica para resolver problemas con subproblemas superpuestos. Cada subproblema se resuelve sólo una vez y el resultado de cada subproblema se almacena en una tabla (generalmente implementada como un array o una tabla hash) para referencias futuras. Estas sub-soluciones pueden ser utilizadas para obtener la solución original y la técnica de almacenar las soluciones de subproblemas se conoce como memorización.

Puedes pensar en DP = recursión + reutilización

Un ejemplo clásico para entender la diferencia sería ver ambos enfoques para obtener el enésimo número de Fibonacci. Revisa este material de MIT.

Enfoque Divide and Conquer

Enfoque de Programación Dinámica

A veces, al programar de forma recursiva, llamas a la función con los mismos parámetros múltiples veces, lo cual es innecesario.

El famoso ejemplo de los números Fibonacci:

           índice: 1,2,3,4,5,6...
número Fibonacci: 1,1,2,3,5,8...

function F(n) {
    if (n < 3)
        return 1
    else
        return F(n-1) + F(n-2)
}

Vamos a ejecutar F(5):

F(5) = F(4) + F(3)
     = {F(3) + F(2)} + {F(2) + F(1)}
     = {[F(2) + F(1)] + 1} + {1 + 1}
     = 1 + 1 + 1 + 1 + 1

Entonces hemos llamado: 1 vez a F(4) 2 veces a F(3) 3 veces a F(2) 2 veces a F(1)

Enfoque de Programación Dinámica: si llamas a una función con el mismo parámetro más de una vez, guarda el resultado en una variable para acceder directamente a él la próxima vez. La forma iterativa:

if (n==1 || n==2)
    return 1
else
    f1 = 1, f2 = 1
    for i = 3 to n
         f = f1 + f2
         f1 = f2
         f2 = f

Volviendo a llamar a F(5):

fibo1 = 1
fibo2 = 1 
fibo3 = (fibo1 + fibo2) = 1 + 1 = 2
fibo4 = (fibo2 + fibo3) = 1 + 2 = 3
fibo5 = (fibo3 + fibo4) = 2 + 3 = 5

Como puedes ver, cuando necesitas hacer múltiples llamadas, simplemente accedes a la variable correspondiente para obtener el valor en lugar de recalcularlo.

Por cierto, programación dinámica no significa convertir un código recursivo en un código iterativo. También puedes guardar los subresultados en una variable si deseas un código recursivo. En este caso, la técnica se llama memoización. Para nuestro ejemplo, se vería así:

// declarar e inicializar un diccionario
var dict = new Dictionary();
for i = 1 to n
    dict[i] = -1

function F(n) {
    if (n < 3)
        return 1
    else
    {
        if (dict[n] == -1)
            dict[n] = F(n-1) + F(n-2)

        return dict[n]                
    }
}

Entonces la relación con Divide y Vencerás es que los algoritmos D&D se basan en la recursión. Y algunas versiones de ellos tienen este problema de "llamada múltiple a la función con el mismo parámetro". Busca ejemplos como "multiplicación de cadenas de matrices" y "subsecuencia común más larga" donde se necesita DP para mejorar el T(n) del algoritmo D&D.

La otra diferencia entre dividir y conquistar y la programación dinámica podría ser:

Divide y conquista:

1. Hace más trabajo en los subproblemas y, por lo tanto, consume más tiempo.
2. En la división y conquista, los subproblemas son independientes entre sí.

Programación dinámica:

1. Resuelve los subproblemas solo una vez y luego los guarda en la tabla.
2. En la programación dinámica, los subproblemas no son independientes.

Considero Divide & Conquer como un enfoque recursivo y Dynamic Programming como llenado de tablas.

Por ejemplo, Merge Sort es un algoritmo de Divide & Conquer, ya que en cada paso se divide el array en dos mitades, se llama recursivamente a Merge Sort en las dos mitades y luego se fusionan.

Knapsack es un algoritmo de Dynamic Programming ya que se llena una tabla que representa soluciones óptimas a subproblemas de la mochila completa. Cada entrada en la tabla corresponde al valor máximo que puedes llevar en una bolsa de peso w dado los elementos 1-j.

Supongo que ya has leído Wikipedia y otros recursos académicos sobre esto, así que no reciclaré esa información. También debo mencionar que no soy un experto en informática de ninguna manera, pero compartiré mi opinión sobre mi entendimiento de estos temas...

Programación Dinámica

Descompone el problema en subproblemas discretos. El algoritmo recursivo para la secuencia de Fibonacci es un ejemplo de Programación Dinámica, porque resuelve fib(n) al resolver primero fib(n-1). Para resolver el problema original, resuelve un problema diferente.

Divide y Vencerás

Estos algoritmos típicamente resuelven piezas similares del problema, y luego las juntan al final. Mergesort es un ejemplo clásico de divide y vencerás. La diferencia principal entre este ejemplo y el de Fibonacci es que en mergesort, la división puede ser (teóricamente) arbitraria, y no importa cómo lo dividas, sigues fusionando y ordenando. La misma cantidad de trabajo tiene que ser hecha para mergesortear el array, sin importar cómo lo dividas. Resolver fib(52) requiere más pasos que resolver fib(2).