/*
 * Recursive version (bad, but a guide to writing the dynamic-programming
 * version)
 */

#include <stdio.h>


/* Cost of multiplying from i to j (semi-inclusive), given array of sizes 's' */
int r_mat_prod(int i, int j, int *s)
{
    int k, mincost;
    if (j == i + 1)
        return 0;
    k = i + 1;
    mincost = r_mat_prod(i, k, s) + r_mat_prod(k, j, s) + s[i]*s[k]*s[j];
    for (k++; k < j; k++) {
        int subcost = r_mat_prod(i, k, s) + r_mat_prod(k, j, s) + s[i]*s[k]*s[j];
        if (subcost < mincost)
            mincost = subcost;
    }
    return mincost;
}


int main()
{
    /* the example from the readings */
    #define n 6
    int s[n+1] = { 4, 2, 3, 1, 2, 2, 3 };

    /* print 'em all, why not... easier to look through and understand */
    /* (after all, this is just a dinky test program, not part of the alg */
    int i, j;
    for (i = 0; i < n; i++)
        for (j = i + 1; j <= n; j++)
            printf("r_mat_prod(%d, %d, s) == %d\n", i, j, r_mat_prod(i, j, s));
    return 0;
}