Programación Dinámica en Java

La programación dinámica se usa típicamente para optimizar algoritmos recursivos, ya que tienden a escalar exponencialmente. La idea principal es desglosar problemas complejos (c...

Introducción

La Programación Dinámica se usa típicamente para optimizar algoritmos recursivos, ya que tienden a escalar exponencialmente. La idea principal es dividir problemas complejos (con muchas llamadas recursivas) en subproblemas más pequeños y luego guardarlos en la memoria para que no tengamos que volver a calcularlos cada vez que los usamos.

¿Qué es la programación dinámica?

La programación dinámica es un principio de programación en el que un problema muy complejo se puede resolver dividiéndolo en subproblemas más pequeños. Este principio es muy similar a la recursividad, pero con una diferencia clave, cada subproblema distinto debe resolverse solo una vez.

Para entender lo que esto significa, primero tenemos que entender el problema de resolver las relaciones de recurrencia. Cada problema complejo se puede dividir en subproblemas muy similares, lo que significa que podemos construir una relación de recurrencia entre ellos.

¡Echemos un vistazo a un ejemplo con el que todos estamos familiarizados, la secuencia de Fibonacci! La sucesión de Fibonacci se define con la siguiente relación de recurrencia:

$$
fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)
$$

Nota: Una relación de recurrencia es una ecuación que define recursivamente una secuencia donde el siguiente término es una función de los términos anteriores. La secuencia de Fibonacci es un gran ejemplo de esto.

Entonces, si queremos encontrar el número ’n-ésimo’ en la secuencia de Fibonacci, debemos conocer los dos números que preceden al ’n-ésimo’ en la secuencia.

Sin embargo, cada vez que queremos calcular un elemento diferente de la secuencia de Fibonacci, tenemos ciertas llamadas duplicadas en nuestras llamadas recursivas, como se puede ver en la siguiente imagen, donde calculamos Fibonacci(5):

fibonacci_sequence

Por ejemplo, si queremos calcular F(5), obviamente necesitamos calcular F(4) y F(3) como requisito previo. Sin embargo, para calcular F(4), necesitamos calcular F(3) y F(2), lo que a su vez requiere que calculemos F(2) y F(1) para obtener F(3), y pronto.

Esto conduce a muchos cálculos repetidos, que son esencialmente redundantes y ralentizan significativamente el algoritmo. Para resolver este problema, nos estamos introduciendo a la Programación Dinámica.

En este enfoque, modelamos una solución como si fuéramos a resolverla recursivamente, pero la resolvemos desde cero, memorizando las soluciones a los subproblemas (pasos) que tomamos para llegar a la cima.

Por lo tanto, para la sucesión de Fibonacci, primero resolvemos y memorizamos F(1) y F(2), luego calculamos F(3) utilizando los dos pasos memorizados, y así sucesivamente. Esto significa que el cálculo de cada elemento individual de la sucesión es O(1), porque ya conocemos los dos primeros.

A la hora de resolver un problema mediante programación dinámica, tenemos que seguir tres pasos:

  • Determinar la relación de recurrencia que se aplica a dicho problema
  • Inicializar los valores iniciales de la memoria/arreglo/matriz
  • Asegurarse de que cuando hacemos una "llamada recursiva" (acceder a la solución memorizada de un subproblema) siempre esté resuelta de antemano

Siguiendo estas reglas, echemos un vistazo a algunos ejemplos de algoritmos que usan programación dinámica.

Algoritmo de corte de varilla

Comencemos con algo simple:

Dada una barra de longitud n y una matriz que contiene los precios de todas las piezas de tamaño menor que n. Determine el valor máximo que se puede obtener cortando la varilla y vendiendo las piezas.

Solución ingenua {#solución ingenua}

Este problema está prácticamente hecho a medida para la programación dinámica, pero debido a que este es nuestro primer ejemplo real, veamos cuántos incendios podemos iniciar dejando que este código se ejecute:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class naiveSolution {
    static int getValue(int[] values, int length) {
        if (length <= 0)
            return 0;
        int tmpMax = -1;
        for (int i = 0; i < length; i++) {
            tmpMax = Math.max(tmpMax, values[i] + getValue(values, length - i - 1));
        }
        return tmpMax;
    }

    public static void main(String[] args) {
        int[] values = new int[]{3, 7, 1, 3, 9};
        int rodLength = values.length;

        System.out.println("Max rod value: " + getValue(values, rodLength));
    }
}

Producción:

1
Max rod value: 17

Esta solución, aunque correcta, es altamente ineficiente. Las llamadas recursivas no se memorizan, por lo que el código pobre tiene que resolver el mismo subproblema cada vez que hay una única solución superpuesta.

Enfoque dinámico

Utilizando el mismo principio básico anterior, pero agregando memoización y excluyendo las llamadas recursivas, obtenemos la siguiente implementación:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public class dpSolution {
    static int getValue(int[] values, int rodLength) {
        int[] subSolutions = new int[rodLength + 1];

        for (int i = 1; i <= rodLength; i++) {
            int tmpMax = -1;
            for (int j = 0; j < i; j++)
                tmpMax = Math.max(tmpMax, values[j] + subSolutions[i - j - 1]);
            subSolutions[i] = tmpMax;
        }
        return subSolutions[rodLength];
    }

    public static void main(String[] args) {
        int[] values = new int[]{3, 7, 1, 3, 9};
        int rodLength = values.length;

        System.out.println("Max rod value: " + getValue(values, rodLength));
    }
}

Producción:

1
Max rod value: 17

Como podemos ver, las salidas resultantes son las mismas, solo que con diferente complejidad de tiempo/espacio.

Eliminamos la necesidad de llamadas recursivas resolviendo los subproblemas desde cero, utilizando el hecho de que todos los subproblemas anteriores a un problema dado ya están resueltos.

Mejora del rendimiento

Solo para dar una perspectiva de cuánto más eficiente es el enfoque dinámico, intentemos ejecutar el algoritmo con 30 valores.

La solución Naive tardó ~5,2 s en ejecutarse, mientras que la solución Dynamic tardó ~0,000095 s en ejecutarse.

Problema de mochila simplificado

El problema de la mochila simplificada es un problema de optimización, para el cual no existe una solución única. La pregunta para este problema sería: "¿Existe alguna solución?":

Dado un conjunto de artículos, cada uno con un peso w1, w2... determinar el número de cada artículo a poner en una mochila para que el peso total sea menor o igual a un límite dado K .

Entonces, demos un paso atrás y averigüemos cómo representaremos las soluciones a este problema. Primero, almacenemos los pesos de todos los elementos en una matriz W.

A continuación, digamos que hay n elementos y los enumeraremos con números del 1 al n, por lo que el peso del elemento i-th es W[i].

Formaremos una matriz M de dimensiones (n+1)x(K+1). M[x][y] correspondiente a la solución del problema de la mochila, pero solo incluye los primeros elementos x del arreglo inicial, y con una capacidad máxima de y.

Ejemplo

Digamos que tenemos 3 artículos, con los pesos w1=2kg, w2=3kg y w3=4kg.

Utilizando el método anterior, podemos decir que M[1][2] es una solución válida. Esto significa que estamos tratando de llenar una mochila con una capacidad de 2 kg con solo el primer elemento de la matriz de peso (w1).

Mientras que en M[3][5] intentamos llenar una mochila con una capacidad de 5 kg utilizando los primeros 3 elementos de la matriz de peso (w1,w2,w3). Esta no es una solución válida, ya que la estamos adaptando.

Inicialización de matriz

Hay 2 cosas a tener en cuenta al llenar la matriz:

¿Existe una solución para el subproblema dado (M[x][y].exists) Y la solución dada incluye el último elemento agregado a la matriz (M[x][y]. incluye).

Por lo tanto, la inicialización de la matriz es bastante fácil, M[0][k].exists siempre es falso, si k > 0, porque no pusimos ningún artículo en una mochila con k capacidad.

Por otro lado, M[0][0].exists = true, porque la mochila debería estar vacía para empezar ya que k = 0, y por lo tanto no podemos poner nada in y esta es una solución válida.

Además, podemos decir que M[k][0].exists = true pero también M[k][0].includes = false para cada k.

Nota: El hecho de que exista una solución para un M[x][y] dado, no significa necesariamente que esa combinación en particular sea la solución. En el caso de M[10][0], existe una solución, que no incluye ninguno de los 10 elementos. Por eso M[10][0].exists = true pero M[10][0].includes = false.

Principio del algoritmo

A continuación, construyamos la relación de recurrencia para M[i][k] con el siguiente pseudocódigo:

1
2
3
4
5
6
7
8
9
if (M[i-1][k].exists == True):
    M[i][k].exists = True
    M[i][k].includes = False
elif (k-W[i]>=0):
    if(M[i-1][k-W[i]].exists == true):
        M[i][k].exists = True
        M[i][k].includes = True
else:
    M[i][k].exists = False

Entonces, la esencia de la solución es dividir el subproblema en dos casos:

  1. Cuando existe una solución para los primeros elementos i-1, para la capacidad k
  2. Cuando existe una solución para los primeros elementos i-1, pero para la capacidad k-W[i]

El primer caso se explica por sí mismo, ya tenemos una solución al problema.

El segundo caso se refiere a conocer la solución para los primeros elementos i-1, pero la capacidad es con exactamente un elemento i-ésimo antes de estar lleno, lo que significa que solo podemos agregar un elemento i-ésimo, y tenemos una nueva solución!

Implementación

En esta implementación, para facilitar las cosas, crearemos la clase Elemento para almacenar elementos:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Element {
    private boolean exists;
    private boolean includes;

    public Element(boolean exists, boolean includes) {
        this.exists = exists;
        this.includes = includes;
    }

    public Element(boolean exists) {
        this.exists = exists;
        this.includes = false;
    }

    public boolean isExists() {
        return exists;
    }

    public void setExists(boolean exists) {
        this.exists = exists;
    }

    public boolean isIncludes() {
        return includes;
    }

    public void setIncludes(boolean includes) {
        this.includes = includes;
    }
}

Ahora podemos sumergirnos en la clase principal:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Knapsack {
    public static void main(String[] args) {
        Scanner scanner = new Scanner (System.in);

        System.out.println("Insert knapsack capacity:");
        int k = scanner.nextInt();

        System.out.println("Insert number of items:");
        int n = scanner.nextInt();

        System.out.println("Insert weights: ");
        int[] weights = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            weights[i] = scanner.nextInt();
        }

        Element[][] elementMatrix = new Element[n + 1][k + 1];

        elementMatrix[0][0] = new Element(true);

        for (int i = 1; i <= k; i++) {
            elementMatrix[0][i] = new Element(false);
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                elementMatrix[i][j] = new Element(false);
                if (elementMatrix[i - 1][j].isExists()) {
                    elementMatrix[i][j].setExists(true);
                    elementMatrix[i][j].setIncludes(false);
                } else if (j >= weights[i]) {
                    if (elementMatrix[i - 1][j - weights[i]].isExists()) {
                        elementMatrix[i][j].setExists(true);
                        elementMatrix[i][j].setIncludes(true);
                    }
                }
            }
        }

        System.out.println(elementMatrix[n][k].isExists());
    }
}

Lo único que queda es la reconstrucción de la solución, en la clase anterior, sabemos que una solución EXISTE, sin embargo, no sabemos cuál es.

Para la reconstrucción usamos el siguiente código:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
List<Integer> solution = new ArrayList<>(n);

if (elementMatrix[n][k].isExists()) {
    int i = n;
    int j = k;
    while (j > 0 && i > 0) {
        if (elementMatrix[i][j].isIncludes()) {
            solution.add(i);
            j = j - weights[i];
        }
        i = i - 1;
    }
}

System.out.println("The elements with the following indexes are in the solution:\n" + (solution.toString()));

Producción:

1
2
3
4
5
6
7
8
9
Insert knapsack capacity:
12
Insert number of items:
5
Insert weights:
9 7 4 10 3
true
The elements with the following indexes are in the solution:
[5, 1]

Una variación simple del problema de la mochila es llenar una mochila sin optimizar el valor, pero ahora con cantidades ilimitadas de cada artículo individual.

Esta variación se puede resolver haciendo un simple ajuste a nuestro código existente:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// Old code for simplified knapsack problem
else if (j >= weights[i]) {
    if (elementMatrix[i - 1][j - weights[i]].isExists()) {
        elementMatrix[i][j].setExists(true);
        elementMatrix[i][j].setIncludes(true);
    }
}

// New code, note that we're searching for a solution in the same
// row (i-th row), which means we're looking for a solution that
// already has some number of i-th elements (including 0) in it's solution
else if (j >= weights[i]) {
    if (elementMatrix[i][j - weights[i]].isExists()) {
        elementMatrix[i][j].setExists(true);
        elementMatrix[i][j].setIncludes(true);
    }
}

El problema de la mochila tradicional {#el problema de la mochila tradicional}

Utilizando las dos variaciones anteriores, echemos ahora un vistazo al problema tradicional de la mochila y veamos en qué se diferencia de la variación simplificada:

Dado un conjunto de elementos, cada uno con un peso w1, w2... y un valor v1, v2... determinar el número de cada elemento a incluir en una colección para que el el peso total es menor o igual a un límite dado k y el valor total es tan grande como sea posible.

En la versión simplificada, todas las soluciones eran igual de buenas. Sin embargo, ahora tenemos un criterio para encontrar una solución óptima (también conocida como el mayor valor posible). Tenga en cuenta que esta vez tenemos un número infinito de cada elemento, por lo que los elementos pueden aparecer varias veces en una solución.

En la implementación, usaremos la antigua clase Elemento, con un valor de campo privado agregado para almacenar el mayor valor posible para un subproblema dado:

1
2
3
4
5
6
public class Element {
    private boolean exists;
    private boolean includes;
    private int value;
    // appropriate constructors, getters and setters
}

La implementación es muy similar, con la única diferencia de que ahora tenemos que elegir la solución óptima a juzgar por el valor resultante:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public static void main(String[] args) {
    // Same code as before with the addition of the values[] array
    System.out.println("Insert values: ");
    int[] values = new int[n + 1];

    for (int i=1; i <= n; i++) {
        values[i] = scanner.nextInt();
    }

    Element[][] elementMatrix = new Element[n + 1][k + 1];

    // A matrix that indicates how many newest objects are used
    // in the optimal solution.
    // Example: contains[5][10] indicates how many objects with
    // the weight of W[5] are contained in the optimal solution
    // for a knapsack of capacity K=10
    int[][] contains = new int[n + 1][k + 1];

    elementMatrix[0][0] = new Element(0);

    for (int i = 1; i <= n; i++) {
        elementMatrix[i][0] = new Element(0);
        contains[i][0] = 0;
    }

    for (int i = 1; i <= k; i++) {
        elementMatrix[0][i] = new Element(0);
        contains[0][i] = 0;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            elementMatrix[i][j] = new Element(elementMatrix[i - 1][j].getValue());
            contains[i][j] = 0;

            elementMatrix[i][j].setIncludes(false);
            elementMatrix[i][j].setValue(M[i - 1][j].getValue());

            if (j >= weights[i]) {
                if ((elementMatrix[i][j - weights[i]].getValue() > 0 || j == weights[i])) {
                    if (elementMatrix[i][j - weights[i]].getValue() + values[i] > M[i][j].getValue()) {
                        elementMatrix[i][j].setIncludes(true);
                        elementMatrix[i][j].setValue(M[i][j - weights[i]].getValue() + values[i]);
                        contains[i][j] = contains[i][j - weights[i]] + 1;
                    }
                }
            }

            System.out.print(elementMatrix[i][j].getValue() + "/" + contains[i][j] + "  ");
        }

        System.out.println();
    }

    System.out.println("Value: " + elementMatrix[n][k].getValue());
}

Producción:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
Insert knapsack capacity:
12
Insert number of items:
5
Insert weights:
9 7 4 10 3
Insert values:
1 2 3 4 5
0/0  0/0  0/0  0/0  0/0  0/0  0/0  0/0  0/0  1/1  0/0  0/0  0/0
0/0  0/0  0/0  0/0  0/0  0/0  0/0  2/1  0/0  1/0  0/0  0/0  0/0
0/0  0/0  0/0  0/0  3/1  0/0  0/0  2/0  6/2  1/0  0/0  5/1  9/3
0/0  0/0  0/0  0/0  3/0  0/0  0/0  2/0  6/0  1/0  4/1  5/0  9/0
0/0  0/0  0/0  5/1  3/0  0/0  10/2  8/1  6/0  15/3  13/2  11/1  20/4
Value: 20

Distancia de Levenshtein

Otro muy buen ejemplo del uso de la programación dinámica es Editar distancia o la Distancia de Levenshtein.

La distancia de Levenshtein para 2 cadenas ‘A’ y ‘B’ es el número de operaciones atómicas que necesitamos usar para transformar ‘A’ en ‘B’, que son:

  1. Eliminación de personajes
  2. Inserción de personajes
  3. Sustitución de caracteres (técnicamente es más de una operación, pero en aras de la simplicidad, llamémosla operación atómica)

Este problema se maneja resolviendo metódicamente el problema de las subcadenas de las cadenas iniciales, aumentando gradualmente el tamaño de las subcadenas hasta que sean iguales a las cadenas iniciales.

La relación de recurrencia que usamos para este problema es la siguiente:

$$ lev_{a,b}(i,j)=min\begin{casos} lev_{a,b}(i-1,j)+1\\lev_{ a,b}(i,j-1)+1\\lev_{a,b}(i-1,j-1)+c(a_i,b_j)\end{casos} $\ ps

c(a,b) siendo 0 si a==b, y 1 si a!=b.

Si está interesado en leer más sobre la distancia de Levenshtein, ya lo cubrimos en Python en otro artículo: [Distancia de Levenshtein y similitud de texto en Python](/levenshtein-distance-and-text-similarity-in- python/%3E){objetivo="_blank"}

Implementación

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class editDistance {
    public static void main(String[] args) {
        String s1, s2;
        Scanner scanner = new Scanner(System.in);
        System.out.println("Insert first string:");
        s1 = scanner.next();
        System.out.println("Insert second string:");
        s2 = scanner.next();

        int n, m;
        n = s1.length();
        m = s2.length();

        // Matrix of substring edit distances
        // example: distance[a][b] is the edit distance
        // of the first a letters of s1 and b letters of s2
        int[][] distance = new int[n + 1][m + 1];

        // Matrix initialization:
        // If we want to turn any string into an empty string
        // the fastest way no doubt is to just delete
        // every letter individually.
        // The same principle applies if we have to turn an empty string
        // into a non empty string, we just add appropriate letters
        // until the strings are equal.
        for (int i = 0; i <= n; i++) {
            distance[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            distance[0][j] = j;
        }

        // Variables for storing potential values of current edit distance
        int e1, e2, e3, min;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                e1 = distance[i - 1][j] + 1;
                e2 = distance[i][j - 1] + 1;
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    e3 = distance[i - 1][j - 1];
                } else {
                    e3 = distance[i - 1][j - 1] + 1;
                }
                min = Math.min(e1, e2);
                min = Math.min(min, e3);
                distance[i][j] = min;
            }

        }

        System.out.println("Edit distance of s1 and s2 is: " + distance[n][m]);
    }
}

Producción:

1
2
3
4
5
Insert first string:
man
Insert second string:
machine
Edit distance of s1 and s2 is: 3

Subsecuencia común más larga (LCS)

El problema va de la siguiente manera:

Dadas dos secuencias, encuentre la longitud de la subsecuencia más larga presente en ambas. Una subsecuencia es una secuencia que aparece en el mismo orden relativo, pero no necesariamente contigua.

Aclaración

Si tenemos dos cadenas, s1 = "MICE" y s2 = "MINCE", la subcadena común más larga sería "MI" o "CE", sin embargo, la más larga común * subsecuencia* sería "MICE" porque los elementos de la subsecuencia resultante no tienen que estar en orden consecutivo.

Relación de recurrencia y lógica general

$$ lcs_{a,b}(i,j)=min\begin{casos} lcs_{a,b}(i-1,j)\\lcs_{a, b}(i,j-1)\\lcs_{a,b}(i-1,j-1)+c(a_i,b_j)\end{casos} $$

Como podemos ver, solo hay una ligera diferencia entre la distancia Levenshtein y LCS, específicamente, en el costo de los movimientos.

En LCS, no tenemos costo para la inserción y eliminación de caracteres, lo que significa que solo contamos el costo de la sustitución de caracteres (movimientos diagonales), que tienen un costo de 1 si los dos caracteres de cadena actuales a[i] y b[j] son iguales.

El costo final de LCS es la longitud de la subsecuencia más larga para las 2 cadenas, que es exactamente lo que necesitábamos.

Usando esta lógica, podemos reducir muchos algoritmos de comparación de cadenas a relaciones de recurrencia simples que utilizan la fórmula base de la distancia de Levenshtein.

Implementación

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class LCS {
    public static void main(String[] args) {
        String s1 = new String("Hillfinger");
        String s2 = new String("Hilfiger");
        int n = s1.length();
        int m = s2.length();
        int[][] solutionMatrix = new int[n+1][m+1];
        for (int i = 0; i < n; i++) {
            solutionMatrix[i][0] = 0;
        }
        for (int i = 0; i < m; i++) {
            solutionMatrix[0][i] = 0;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int max1, max2, max3;
                max1 = solutionMatrix[i - 1][j];
                max2 = solutionMatrix[i][j - 1];
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    max3 = solutionMatrix[i - 1][j - 1] + 1;
                } else {
                    max3 = solutionMatrix[i - 1][j - 1];
                }
                int tmp = Math.max(max1, max2);
                solutionMatrix[i][j] = Math.max(tmp, max3);
            }
        }
        
        System.out.println("Length of longest continuous subsequence: " + solutionMatrix[n][m]);
    }
}

Producción:

1
Length of longest continuous subsequence: 8

Otros problemas que utilizan programación dinámica {#otros problemas que utilizan programación dinámica}

Hay muchos más problemas que se pueden resolver con la programación dinámica, estos son solo algunos de ellos:

  • Problema de partición (próximamente)
  • Dado un conjunto de números enteros, averiguar si se puede dividir en dos subconjuntos con sumas iguales
  • Problema de suma de subconjuntos (próximamente)
  • Dado un conjunto de enteros positivos, y un valor suma, determinar si existe un subconjunto del conjunto dado con suma igual a suma dada.
  • Problema de cambio de moneda (Número total de formas de obtener la denominación de las monedas, próximamente)
  • Dado un suministro ilimitado de monedas de denominaciones dadas, encuentre el número total de formas distintas de obtener el cambio deseado.
  • Soluciones totales posibles a la ecuación lineal de las variables k (próximamente)
  • Dada una ecuación lineal de k variables, contar el número total de posibles soluciones de la misma.
  • Encuentra la probabilidad de que un borracho no se caiga por un precipicio (Niños, no intenten esto en casa)
  • Dado un espacio lineal que representa la distancia desde un precipicio, y sabiendo la distancia inicial del borracho desde el precipicio, y su tendencia a ir hacia el precipicio p y alejarse del precipicio 1-p, calcule el probabilidad de su supervivencia.
  • Mucho mas...

Conclusión

La programación dinámica es una herramienta que puede ahorrarnos mucho tiempo computacional a cambio de una mayor complejidad espacial, dado que algunos de ellos solo llegan a la mitad (se necesita una matriz para la memorización, pero se usa una matriz que cambia constantemente) .

Esto depende en gran medida del tipo de sistema en el que esté trabajando, si el tiempo de CPU es precioso, opta por una solución que consuma memoria, por otro lado, si su memoria es limitada, opta por una solución que consume más tiempo. para una mejor relación complejidad tiempo/espacio.