Programación dinámica y codiciosa

Los artículos escritos en este blog fueron creados con el objetivo de enseñar. Además, la información del artículo puede ser incorrecta, así que tenga cuidado.

La Programación Dinámica y Greedy dividen los grandes problemas en opciones más pequeñas, pero abordan las opciones de manera diferente.

Dynamic Programming

Se utiliza cuando se repite el mismo problema pequeño y se puede crear la solución óptima al problema grande con la solución óptima al problema pequeño.

int Fibonacci(int N)
{
    if (N <= 1)
    {
        return N;
    }

    std::vector<int> DP(N + 1, 0);
    DP[1] = 1;

    for (int i = 2; i <= N; ++i)
    {
        DP[i] = DP[i - 1] + DP[i - 2];
    }

    return DP[N];
}

Como los resultados calculados se almacenan, no se repite el mismo problema recursivo. La clave es establecer adecuadamente definiciones de estado y expresiones de ignición.

Greedy

Haz la elección que te parezca mejor en el momento presente y no retrocedas en tu elección anterior.

Al igual que el problema de selección de actividades, hay problemas en los que la solución óptima se logra seleccionando continuamente la tarea con el tiempo de finalización más rápido. Sin embargo, en el problema de cambio en el que las unidades monetarias se dan de forma arbitraria, seleccionar primero la moneda más grande puede no ser lo óptimo.

Monedas: 1, 3, 4
Cantidad: 6

Codicioso: 4 + 1 + 1 = 3
Solución óptima: 3 + 3 = 2

Greedy es rápido y utiliza poca memoria, pero requiere pruebas de que la selección óptima local conduce a una solución óptima global. Si elige Greedy solo porque algunos ejemplos son correctos, fallará en los contraejemplos.