function cost = matrix_chain ( dims )

%*****************************************************************************80
%
%% matrix_chain() finds the lowest cost to form a multiple matrix product.
%
%  Discussion:
%
%    This code represents a dynamic programming approach from 
%    a Wikipedia article.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    30 December 2023
%
%  Author:
%
%    John Burkardt
%
%  Reference:
%
%    Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein,
%    Introduction to Algorithms,
%    MIT Press, 2001,
%    ISBN: 978-0-262-03293-3,
%    LC: QA76.C662.
%
%  Input:
%
%    integer dims(n+1): matrix dimension information.  Matrix A(i)
%    has dimensions dims(i) x dims(i+1).  All entries must be positive.
%
%  Output:
%
%    integer cost: the minimal cost, in terms of scalar multiplications,
%    for the optimal ordering of the matrix multiplications.
%
  cost = 0;
%
%  N is the number of matrices in the product.
%
  n = length ( dims ) - 1;
  if ( n < 2 )
    return
  end

  if ( any ( dims <= 0 ) )
    return
  end
%
%  m[i,j] = Minimum number of scalar multiplications (i.e., cost)
%  needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
%  The cost is zero when multiplying one matrix.
%
%  K is the index of the subsequence split that achieved minimal cost
%
  m = Inf * ones ( n, n );
  for i = 1 : n
    m(i,i) = 0;
  end

  for len = 2 : n
    for i = 1 : n + 1 - len
      j = i - 1 + len;
      for k = i : j - 1
        cost = m(i,k) + m(k+1,j) + dims(i) * dims(k+1) * dims(j+1);
        if ( cost <= m(i,j) )
          m(i,j) = cost;
          s(i,j) = k; 
        end
      end
    end
  end

  return
end

