Skip to content

Matrix chain multiplications type problem

description

  • you are given an array, or a string
  • you have to calculate something which depends on the subarray between the range

recursive code

#include <bits/stdc++.h>
using namespace std;

// state -> (i, j)
int solve(vector<int> p, int i, int j) {
    if (i == j) return 0; // base condition
    int min = INT_MAX; // answer to return
    for (int k = i; k < j; k++) { // check all sub arrays
        // split array into tow subarray
        int count = solve(p, i, k) + 
                    solve(p, k + 1, j) + 
                    p[i - 1] * p[k] * p[j]; // cost of combining two subarray
        if (count < min) min = count;
    }
    return min;
}

int main(){
    vector<int> arr = { 1, 2, 3, 4, 3 };
    cout << solve(arr, 1, arr.size() - 1);
    return 0;
}

memoization sol

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> dp;
int solve(vector<int> p, int i, int j) {
    if (i == j) return 0; // base condition
    if(dp[i][j] != -1) return dp[i][j];
    int min = INT_MAX; // answer to return
    for (int k = i; k < j; k++) { // check all sub arrays
        // split array into tow subarray
        int count = solve(p, i, k) + 
                    solve(p, k + 1, j) + 
                    p[i - 1] * p[k] * p[j]; // cost of combining two subarray
        if (count < min) min = count;
    }
    return dp[i][j] = min;
}

int main(){
    vector<int> arr = { 1, 2, 3, 4, 3 };
    int n = arr.size();
    dp = vector<vector<int>> (n+1, vector<int> (n+1, -1));
    cout << solve(arr, 1, n - 1);
    return 0;
}

top down approach

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> p) {
    int n = p.size();
    vector<vector<int>> dp(n+1, vector<int> (n+1, 0));

    // length of subarray you will traverse
    for(int len=2;len<n+1;len++){
        for(int i=1;i<= n-len+1; i++){
            int j=i+len-1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int count = dp[i][k] + dp[i+1][k] + p[i - 1] * p[k] * p[j];
                dp[i][j] = min(dp[i][j], count);
            }
        }
    }
    return dp[n][b];
}

int main(){
    vector<int> arr = { 1, 2, 3, 4, 3 };
    int n = arr.size();
    cout << solve(arr, 1, n - 1);
    return 0;
}

practice question