[Estrategias] Programación Dinámica vs Divide y conquistarás (DUDA)

[GGZ]

Hola a todos, la pregunta es bien directa.

No entiendo bien la diferencia entre Programación Dinámica(botton up y top-down)
¿Alguien me podría dar ejemplos de códigos explicando la lógica de cada uno?


¡Saludos!

[MAFUS]

No hay mucho código que mostrar porque eso es técnicas de diseño.

[GGZ]

Si que los hay, y los encontré ya los voy entendiendo de todos modos ...

Top-Down y Botton-Up para calcular un número combinatorio.

Código (c) [Seleccionar] Expandir


int comb(int n, int k) {
 static int table[MAXN][MAXK] = { 0 };

 if (k == 0 || n == k)
   return 1;

 if (table[n][k] != 0)
   return table[n][k];

 table[n][k] = comb(n - 1, k) + comb(n - 1, k - 1);

 return table[n][k];
}


Código (c) [Seleccionar] Expandir


int comb_(int n, int k) {
 int table[n+1][k+1];
 int i, j;

 for (i = 0; i <= n; i++)
   table[i][0] = 1;

 for (i = 0; i <= n; i++)
   table[i][i] = 1;

 for (i = 0; i <= n; i++)
   for (j = 1; j <= k && j < i; j++){
printf ("Valor de i: %d, valor de j: %d\n",i,j);
     table[i][j] = table[i - 1][j - 1] + table[i - 1][j];

}

 return table[n][k];
}


[MAFUS]

Eso muestra una solución recursiva y su contraparte iterativa.

Top-down y bottom-up son como te explica, por ejemplo, wikipedia: https://es.wikipedia.org/wiki/Top-down_y_bottom-up

[GGZ]

A eso era que me refería pero ya fue, a mi me lo dieron así.

Wikipedia es lo primero que leí antes de escribir este post.

Fue, ya está.
¡Saludos!