Qué es la programación dinámica (divide y vencerás v2.0)

La programación dinámica es una técnica de diseño de algoritmos que busca mejorar la complejidad en tiempo de la solución de un problema que se pueda plantear desde una filosofía recursiva, empleando la reutilización de las soluciones ya obtenidas con una estructura de datos auxiliar, cuyos elementos representan sub-problemas específicos (según cómo se determine). Puede ser top-down (desde lo más general hacia abajo, requiere un manejo recursivo empleando “memoization”), o bien bottom-up (iterativo, partiendo del problema trivial hasta el problema más general)

El procedimiento que se sigue para plantear la solución de programación dinámica a un problema es el siguiente:

1. Identificar los problemas triviales del problema, a partir de los cuales se puedan generalizar luego problemas más complejos

2. Verificar cuáles problemaas están apenas un nivel más alto que el trivial, e inducir una generalización recursiva (y de optimización, si es el caso) para éstos

3. Determinar finalmente la respuesta de los problemas generalizados a partir de la estructura de datos que contiene las soluciones calculadas

En problemas de optimización, la estructura de datos de apoyo almacena las soluciones óptimas a los problemas de decisión (de los problemas triviales a los más generales); de este modo, para establecer la solución general hay que basarse en las decisiones de optimización que quedan reflejadas en dicha estructura (recorriendo desde los problemas triviales hasta el más general, tomando nota de los elementos a los que corresponden los valores óptimos, información que es proporcionada por los índices de las casillas a los que corresponden los problemas particulares)

• Ejemplo 1: Factorial

  Primero se identifican los problemas triviales:

    factorial de 0 = 1
    factorial de 1 = 1
  

  Luego se induce una generalización partiendo de problemas apenas mayores a los triviales:

    factorial de 2 = 2 * factorial de 1
  
    factorial de 3 = 3 * factorial de 2
  
    ...
  
    factorial de N = N * factorial de N-1
  

  Se define la estructura solución:

    solucion[i] = factorial de i
  

  El algoritmo queda:

    funcion factorial(N : entero) : entero
  
    	soluciones <- Nuevo arreglo de enteros tamaño N
  
    	solucion[0] <- 0		// Solucion trivial
  
    	solucion[1] <- 1 		// Solucion trivial
  
    	para i <- 2 hasta N
  
    		solucion[i] <- i * solucion[i-1]		// Solucion general
  
    	retorna solucion[N] 	// Solucion final
  

• Ejemplo 2: Elemento de la secuencia de Fibonacci

  Problemas triviales:

    Fibonacci de 0 = 1
  
    Fibonacci de 1 = 1 
  

  Generalización:

    Fibonacci de 2 = Fibonacci de 1 + Fibonacci de 0
  
    Fibonacci de 3 = Fibonacci de 2 + Fibonacci de 1
  
    ...
  
    Fibonacci de N = Fibonacci de N-1 + Fibonacci de N-2
  

  Se define la estructura solución:

    solucion[i] = Fibonacci de i
  

  Algoritmo:

    funcion fibonacci(N : entero) : entero
  
    	solucion <- Nuevo arreglo de tamaño N
  
    	solucion[0] <- 1
  
    	solucion[1] <- 1
  
    	para i <-2 hasta N
  
    		solucion[i] <- solucion[i-1] + solucion[i-2]
  
    	return solucion[N]

Aprendiendo Dynamic Programming con JS porque el entrevistador me lo ordenó -parte 1

para que calcular algo muchas veces si ya lo calcule una vez ??
programación dinámica = recursividad + memorización
simple y muy eficiente

LA PROGRAMACIÓN DINÁMICA:
Es un concepto importante, es un método para resolver problemas grandes y complejos esta programación dinámica agrega una cosa mas y es cada uno de los subproblemas que se van resolviendo, se va a ir guardando automáticamente y ahí esta lo dinámico.
El programa lleva la cuenta de todos los cálculos o ordenamientos y cuando le agregas una nueva operación simplemente la acumula dinamicamente.

La principal ventaja que tiene la programación dinámica contra el paradigma de Divide y Venceras es que memoiza los resultados, memoizar, significa que guarda en memoria un resultado calculado previamente, lo que hace que por ejemplo si existen sub problemas “solapados” es decir sub problemas que ya hemos calculado antes, pues no los vuelve a calcular, lo que lo hace mas eficiente.

En pocas palabras la programación dinamica es un método de otpimización matematica en el que se pueden seguir agregando datos.

Acá un ejemplo con de las serie fibonacci con programación dinámica en Java

public class Fibonacci {

    Map<Integer, Integer> memory = new HashMap<Integer, Integer>();

    public int fibonacci(int n){
        if (n == 0) return 0;
        if (n == 1) return 1;

        if (memory.get(n) != null){
            return memory.get(n);
        }
        memory.put(n, fibonacci(n-1) + fibonacci(n-2));
        return memory.get(n);

    }

}

Merge Sort en JS:

function merge(leftArr, rightArr) {
var sortedArr = [];
  while (leftArr.length && rightArr.length) {
    if (leftArr[0] <= rightArr[0]) {
      sortedArr.push(leftArr[0]);
      leftArr = leftArr.slice(1)
   } else {
      sortedArr.push(rightArr[0]);
      rightArr = rightArr.slice(1)
     }
   }
  while (leftArr.length)
    sortedArr.push(leftArr.shift());
  while (rightArr.length)
    sortedArr.push(rightArr.shift());
  return sortedArr;
}
function mergesort(arr) {
  if (arr.length < 2) {
    return arr; }
  else {
    var midpoint = parseInt(arr.length / 2);
    var leftArr   = arr.slice(0, midpoint);
    var rightArr  = arr.slice(midpoint, arr.length);
    return merge(mergesort(leftArr), mergesort(rightArr));
  }
}
let unsortedArr = [340, 1, 3, 3, 76, 23, 4, 12, 122, 7642, 646];
console.log('This should be the sorted array!')
console.log(mergesort(unsortedArr));```

Tratando de entender programación dinámica, encontré esta liga que puede servir:
No memoización

Y bueno, adjunto código del Merge Sort para C, antes de pasar a la propia clase:

#include <stdio.h>

void merge(int izq[], int c_izq, int der[], int c_der, int original[])
{
    int i, j, k;
    i = j = k = 0; 
    while(i < c_izq && j < c_der)
    {
        if(izq[i] <= der[j])
        {
            original[k] = izq[i];
            i++;
        }
        else
        {
            original[k] = der[j];
            j++;
        }
        k++;
    }
    while(i < c_izq)
    {
        original[k] = izq[i];
        i++;
        k++;
    }
    while(j < c_der)
    {
        original[k] = der[j];
        j++;
        k++;
    }
}

void mergeSort(int original[], int tam)
{
    if(tam < 2)
        return;
    else
    {
        int mitad = tam/2;
        int izq[mitad], der[tam-mitad];
        for(int i=0; i<mitad; i++)
            izq[i] = original[i];
        for(int i=mitad; i<tam; i++)
            der[i-mitad] = original[i];
        int tam_izq = sizeof(izq)/sizeof(izq[0]);
        int tam_der = sizeof(der)/sizeof(der[0]);
        mergeSort(izq, mitad);
        mergeSort(der, tam-mitad);
        merge(izq, tam_izq, der, tam_der, original);
    }    
}

void main()
{
    int original[]={9000, 8888, 6677, 5544, 5500, 3333, 222, 11, 0};
    int e = sizeof(original)/sizeof(original[0]);
    printf("\nArreglo desordenado: \n");
    for(int i=0; i<e; i++)
        printf("%d ", original[i]);
    mergeSort(original, e);
    printf("\n\nArreglo ordenado (ascendente): \n");
    for(int i=0; i<e; i++)
        printf("%d ", original[i]);
    printf("\n\nFin.");        
}

Aquí lo puedes ver funcionando.

let array = [100, 4, 3, 5, 6, 5, 7, 7, 10, 13, 25]

    let parte1 = array.splice(0, (array.length/2))
    let parte2 = array.splice(0, array.length)

    for(i = 0; i < parte1.length; i++){
      if(parte1[i] > parte1[i+1]){
        let temp = parte1[i]
        parte1[i] = parte1[i+1]
        parte1[i+1] = temp
      }
    }

    for(i = 0; i < parte2.length; i++){
      if(parte2[i] > parte2[i+1]){
        let temp = parte2[i]
        parte2[i] = parte2[i+1]
        parte2[i+1] = temp
      }
    }


    let merge = parte1.concat(parte2)

    for(i = 0; i < merge.length; i++){
      if(merge[i] > merge[i+1]){
        let temp = merge[i]
        merge[i] = merge[i+1]
        merge[i+1] = temp
      }
    }

    document.write(merge)```

interesante, me gustaria aplicarlo y praticar mas

Gran método de optimización en el programa que lo hace ser dinámico.

Es esta version 2.0, cada uno de los subproblemas, se van guardando y acomodando automátcamente.

Divide and conquer: (divide y vencerás) divide, vence y combina.
programación dinámica: cada vez que desarrollamos o resolvemos un problema se irá implementando automáticamente.

Programación dinámica es como divide and conquer, pero sin el paso de combinar ya que esta lo hace automáticamente

• Merge Sort Algorithm: Divide and Conquer and Combine.
• Quicksort Algorithm: Divide and Conque using Dynamic Programming

La programación dinámica es un método para resolver problemas complejos, ya que los divide en problemas más pequeños, los resuelve y conforme va resolviendo lo va acomodando para la resolución del problema final.

analizar un problema y descomponerlo en problemas mas pequeños

Programación dinámica: En informática, la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas.

Según este artículo en Wikipedia, Quick Sort no es un problema de de programación dinámica.

Resumen:

• Romper el problema en subproblemas más pequeños.
• La combinación de las (sub)soluciones no se hace al final, sino que se va haciendo a medida que se van resolviendo los subproblemas.

using System;
class SortingWithMerge{
  static void Main() {
      int[] arr = {47,-854,852,1,-99,0,-9999,9,10,8};
      
       MergeSort(arr, 0, arr.Length-1);
      
       foreach(int num in arr)
       {
           
            Console.WriteLine(num);
       }
  }
  
   
   
    public static void MergeSort(int[] arr, int low, int high)
    {
        if( high > low)
        {
            int mid = (low + high) / 2;
             
            MergeSort(arr, low, mid);
            MergeSort(arr, (mid+1), high);
            Merge(arr, low, mid, high);
        }
    }
     
    public static void Merge(int[] arr, int low, int mid, int high)
    {
        int[] temp = new int[arr.Length];
        int i = low;
        int j = mid +1;
        int k = low;
        int elementNum = (high - low +1);
            
        while(i <= mid && j <= high)
        {
            if(arr[i] <= arr[j])
            {
                temp[k] = arr[i];
                i++;
            }
            else
            {
                temp[k] = arr[j];
                j++;
            }
            
            k++;
        }
            
        while(i <= mid)
        {
            temp[k] = arr[i];
            i++;
            k++;
        }
        
         while(j <= high)
        {
            temp[k] = arr[j];
            j++;
            k++;
        }
        
        for( int n = 0; n<elementNum; n++ )
        {
            arr[high] = temp[high] ;
            high--;
        }
    }
}
``

Se aplica mucho en programacion, excelente

gracias

function quickSort(array) {
    if (array.length < 1) {
        return [];
    }
    var left = [];
    var right = [];
    var pivot = array[0];

    for (var i = 1; i < array.length; i++){
       if (array[i] < pivot){
           if (array[i] < pivot){
               left.push(array[i]);
           } else {
               right.push(array[i]);
           }
       } 
       return [].concat(quickSort(left), pivot, quickSort(right));
    }
}

console.log(quickSort([4, 9, 2, 1, 6, 3, 8]));```

Interesante añadido al paradigma “divide y vencerás”, añadimos un concepto de memoria. Nos ahorramos la combinación.

Programación dinámica
Método para resolver problemas complejos, rompiéndolos en un conjunto de problemas simples.

Dividir, Conquistar y Combinar

Dividir: Tomar un problema grande en subproblemas
Conquistar: Resolver cada uno de los subproblemas
Combinar: Unir apropiadamente las respuestas

“Know your history or be doomed to repeat it”

Wuaooo me quedo muchísimo más claro!! gracias!!

1. Mis apuntes sobre: “Qué es la programación dinámica” (divide y vencerás v2.0)
   Programación dinámica: Método para resolver problemas complejos, rompiéndolo en una colección de problemas simples, cada uno de los subproblemas se va a ir guardando y acomodando.

Hace un tiempo vi la implementación del factorial de un número, usando este concepto, y hasta ahora me entero de que es programación dinámica D:. Excelente explicación.

“Problemas que solucionamos se van a ir guardando automáticamente y se va a ir acomodando automáticamente”

Cuando un profesor dice un concepto y se ríe lo mas probable es que eso vaya en el examen jejeje