Dynamic Programming

Matrix Chain Multiplication

int mcm(vector<int>& arr, int i, int j) {
    if(i+1 == j) return 0;
    int res = INT_MAX;
    for(int k = i+1; i < n; i++) {
        int curr = minMultiRec(arr,i,k) + minMultiRec(arr, k, j) + arr[i] * arr[k] * arr[j];
        res = min(curr, res);
    }
    return res;
}

int matrixMultiplication(vector<int>& arr) {
    int n = arr.size();
    return mcm(arr, 0, n-1);
}