# include <cstdlib>
# include <iomanip>
# include <iostream>

using namespace std;

# include "matrix_chain_dynamic.hpp"

//****************************************************************************80

int catalan_number ( int n )

//****************************************************************************80
//
//  Purpose:
//
//    catalan_number() computes the N-th Catalan number.
//
//  Licensing:
//
//    This code is distributed under the MIT license. 
//
//  Modified:
//
//    23 April 2024
//
//  Author:
//
//    John Burkardt
//
//  Input:
//
//    int N, the index of the Catalan number.
//
//  Output:
//
//    int C, the value of the Catalan number.
//
{
  int c;
  int i;

  if ( n < 0 )
  {
    c = 0;
    return c;
  }

  c = 1;
//
//  The extra parentheses ensure that the integer division is
//  done AFTER the integer multiplication.
//
  for ( i = 1; i <= n; i++ )
  {
    c = ( c * 2 * ( 2 * i - 1 ) ) / ( i + 1 );
  }

  return c;
}
//****************************************************************************80

bool i4vec_is_nonpositive_any ( int n, int a[] )

//****************************************************************************80
//
//  Purpose:
//
//    i4vec_is_nonpositive_any(): ( any ( A <= 0 ) ).
//
//  Discussion:
//
//    An I4VEC is a vector of I4's.
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    01 January 2023
//
//  Author:
//
//    John Burkardt
//
//  Input:
//
//    int n: the number of entries.
//
//    int a[n]: the vector to check.
//
//  Output:
//
//    bool i4vec_is_nonpositive_any: true if ANY entry is nonpositive.
//
{
  int i;
  bool value;

  value = false;

  for ( i = 0; i < n; i++ )
  {
    if ( a[i] <= 0 )
    {
      value = true;
      break;
    }
  }

  return value;
}
//****************************************************************************80

int matrix_chain_dynamic ( int n, int dims[] )

//****************************************************************************80
//
//  Purpose:
//
//    matrix_chain_dynamic() 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:
//
//    31 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 n: the number of matrices in the product.
//
//    integer dims(n+1): matrix dimension information.  Matrix A(i)
//    has dimensions dims(i) x dims(i+1).  All entries must be positive.
//
//  Output:
//
//    int matrix_chain_dynamic: the minimal cost, in terms of scalar multiplications,
//    for the optimal ordering of the matrix multiplications.
//
{
  int cost;
  int i;
  const int i4_huge = 2147483647;
  int j;
  int k;
  int l;
  int *m;
  int *s;

  cost = 0;
//
//  N is the number of matrices in the product.
//
  if ( n < 2 )
  {
    return cost;
  }

  if ( i4vec_is_nonpositive_any ( n, dims ) )
  {
    return cost;
  }
//
//  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 = new int[n*n];
  s = new int[n*n];

  for ( i = 0; i < n; i++ )
  {
    for ( j = 0; j < n; j++ )
    {
      if ( i == j )
      {
        m[i+j*n] = 0;
      }
      else
      {
        m[i+j*n] = i4_huge;
      }
    }
  }

  for ( l = 2; l <= n; l++ )
  {
    for ( i = 1; i <= n + 1 - l; i++ )
    {
      j = i - 1 + l;
      for ( k = i; k <= j - 1; k++ )
      {
        cost = m[i-1+(k-1)*n] + m[k+(j-1)*n] + dims[i-1] * dims[k] * dims[j];
        if ( cost <= m[i-1+(j-1)*n] )
        {
          m[i-1+(j-1)*n] = cost;
          s[i-1+(j-1)*n] = k - 1;
        }
      }
    }
  }

  delete [] m;
  delete [] s;

  return cost;
}