Improving space complexity in matrix chain multiplication

Question

I want to know whether there is any way to improve space complexity of Dynamic Programming solution of matrix multiplication problem from O(N^2) to something better?

Answer 1

Here is a solution with space compexity O(n)

#include <iostream>

using namespace std;

int min_cost(int a[], int n) {
    int* b = new int(n);

    b[1] = 0;
    b[2] = a[0]*a[1]*a[2];

    for (int j = 3; j < n; j++) {
        b[j] = min( b[j-1] + a[0]*a[j-1]*a[j], b[j-2] + a[j-1]*a[j-2]*a[j] + a[0]*a[j-2]*a[j]);
    }

    return b[n-1];
}

int main() {
    int arr[] = {10, 20, 30};
    int size = sizeof(arr)/sizeof(arr[0]);

    printf("Minimum number of multiplications is %d ", min_cost(arr, size));

   return 0;
}