
-- | example Dynamic Programming (DP) program.

module Main where

import Data.Array.IArray
import System.Environment (getArgs)


run n = arr where
  arr :: Array (Int,Int) Int
  arr = array ((1,1),(n,n)) [ ((i,j),f (i,j)) | i <- [1..n], j <- [1..n]]
  f (i,j)
    | i >  j = n -- "undefined lower triangular part"
    | i == j = i -- initialize the main diagonal
    -- a calculation that does some work
    | otherwise = minimum $ n : [ arr ! (i+1,k) + arr ! (k+1,j-1) | k <- [i+1..j-2]]


main = do
  (a:_) <- getArgs
  let n = read a
  print $ run n ! (1,n)
