/*
 * Dynamic version:
 * cost[i][j] will be the cost of multiplying A_i * A_{i+1} * ... * A_{j­1}
 *
 * This version isn't very good because it just prints out the number 36...
 * see dynamic2.c for a more interesting output.
 */

#include <stdio.h>

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

    int i, len;
    int cost[n+1][n+1];

    for (i = 0; i < n; i++)
        cost[i][i+1] = 0;
    for (len = 2; len <= n; len++) {
        for (i = 0; i + len <= n; i++) {
            int j = i + len;
            int k = i + 1;
            cost[i][j] = cost[i][k] + cost[k][j] + s[i]*s[k]*s[j];
            for (k++; k < j; k++)
                if (cost[i][k] + cost[k][j] + s[i]*s[k]*s[j] < cost[i][j])
                    cost[i][j] = cost[i][k] + cost[k][j] + s[i]*s[k]*s[j];
        }
    }

    printf("%d\n", cost[0][n]);
    return 0;
}