function catalan_number ( n )

!*****************************************************************************80
!
!! catalan_number() computes the Nth Catalan number.
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    23 April 2024
!
!  Author:
!
!    John Burkardt
!
!  Input:
!
!    integer N, the index of the Catalan number.
!
!  Output:
!
!    integer CATALAN_NUMBER: the value of the Catalan number.
!
  implicit none

  integer c
  integer catalan_number
  integer i
  integer n

  if ( n < 0 ) then
    catalan_number = 0
    return
  end if

  c = 1
!
!  The extra parentheses ensure that the integer division is
!  done AFTER the integer multiplication.
!
  do i = 1, n
    c = ( c * 2 * ( 2 * i - 1 ) ) / ( i + 1 )
  end do

  catalan_number = c

  return
end
subroutine matrix_chain_dynamic ( n, dims, cost )

!*****************************************************************************80
!
!! 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:
!
!    integer cost: the minimal cost, in terms of scalar multiplications,
!    for the optimal ordering of the matrix multiplications.
!
  implicit none

  integer n

  integer cost
  integer dims(n+1)
  integer i
  integer j
  integer k
  integer l
  integer m(n,n)
  integer s(n,n)

  cost = 0
!
!  N is the number of matrices in the product.
!
  if ( n < 2 ) then
    return
  end if

  if ( any ( dims <= 0 ) ) then
    return
  end if
!
!  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(1:n,1:n) = huge ( 1 )
  do i = 1, n
    m(i,i) = 0
  end do

  do l = 2, n
    do i = 1, n + 1 - l
      j = i - 1 + l
      do 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) ) then
          m(i,j) = cost
          s(i,j) = k
        end if
      end do
    end do
  end do

  return
end