Untitled

#include <iostream>
#include <vector>
#include <climits>

// Function to print the optimal parenthesized sequence order
void printParenthesis(int i, int j, std::vector<std::vector<int>>& bracket, char& name)
{
    // Base case: when there is only one matrix in the chain
    if (i == j)
    {
        std::cout << name++;
        return;
    }
    
    std::cout << "(";
    
    // Recursively print optimal parenthesized sequence order
    // for matrices from i to bracket[i][j]
    printParenthesis(i, bracket[i][j], bracket, name);
    
    // Recursively print optimal parenthesized sequence order
    // for matrices from bracket[i][j] + 1 to j
    printParenthesis(bracket[i][j] + 1, j, bracket, name);
    
    std::cout << ")";
}

// Function to find the minimum cost required to multiply the matrices
int matrixChainOrder(std::vector<int>& dims)
{
    int n = dims.size() - 1; // number of matrices
    
    // Create matrices to store the minimum cost and optimal
    // parenthesized sequence order
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
    std::vector<std::vector<int>> bracket(n, std::vector<int>(n, 0));
    
    // Compute minimum cost for all chain lengths from 2 to n
    for (int len = 2; len <= n; ++len)
    {
        for (int i = 0; i <= n - len; ++i)
        {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            
            for (int k = i; k < j; ++k)
            {
                // Compute the cost of multiplying matrices from i to k
                // and from k+1 to j, and add them to the cost of multiplying
                // the resulting matrices
                int cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1];
                
                if (cost < dp[i][j])
                {
                    dp[i][j] = cost;
                    bracket[i][j] = k; // Store the index at which the sequence is split
                }
            }
        }
    }
    
    // Print the optimal parenthesized sequence order
    char name = 'A';
    std::cout << "Optimal Parenthesized Sequence Order: ";
    printParenthesis(0, n - 1, bracket, name);
    std::cout << std::endl;
    
    return dp[0][n - 1];
}

int main()
{
    // Input the dimensions of the matrices
    std::vector<int> dims = {10, 100, 5, 50};
    
    // Find the minimum cost required to multiply the matrices
    int minCost = matrixChainOrder(dims);
    
    // Print the minimum cost
    std::cout << "Minimum Cost: " << minCost << std::endl;
    
    return 0;
}