Algoritmia - ALGORITMO DE PARENTIZACIÓN

#include <iostream>

#include <climits>

using namespace std;

// Función para calcular el costo mínimo de parentización de matrices

int costoMinimoParentizacion(int dimensiones[], int n) {

    int dp[n][n];

    // Inicializar la tabla de memoización

    for (int i = 1; i < n; i++) {

        dp[i][i] = 0;

    }

    // Llenar la tabla de memoización de abajo hacia arriba

    for (int longitud = 2; longitud < n; longitud++) {

        for (int i = 1; i < n - longitud + 1; i++) {

            int j = i + longitud - 1;

            dp[i][j] = INT_MAX;

            for (int k = i; k <= j - 1; k++) {

                int costo = dp[i][k] + dp[k + 1][j] + dimensiones[i - 1] * dimensiones[k] * dimensiones[j];

                if (costo < dp[i][j]) {

                    dp[i][j] = costo;

                }

            }

        }

    }

    return dp[1][n - 1];

}

int main() {

    // Ejemplo de uso

    int dimensiones[] = {30, 35, 15, 5, 10, 20, 25};

    int n = sizeof(dimensiones) / sizeof(dimensiones[0]);

    int costoMinimo = costoMinimoParentizacion(dimensiones, n);

    cout << "El costo mínimo de parentización de matrices es: " << costoMinimo << endl;

    return 0;

}