The cheapest order to multiply matrices

def matrix_chain(dims):
    n = len(dims) - 1                          # number of matrices
    cost = [[0] * n for _ in range(n)]         # cost[i][j]: matrices i..j
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            cost[i][j] = min(cost[i][k] + cost[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                             for k in range(i, j))   # k: where the last multiplication splits
    return cost[0][n - 1]

#include <algorithm>
#include <climits>
#include <vector>

long long solve(const std::vector<int>& dims) {
    const int n = dims.size() - 1;
    std::vector<std::vector<long long>> cost(n, std::vector<long long>(n, 0));
    for (int len = 2; len <= n; ++len)
        for (int i = 0; i + len - 1 < n; ++i) {
            int j = i + len - 1;
            cost[i][j] = LLONG_MAX;
            for (int k = i; k < j; ++k)                 // the last split
                cost[i][j] = std::min(cost[i][j], cost[i][k] + cost[k + 1][j] + (long long)dims[i] * dims[k + 1] * dims[j + 1]);
        }
    return cost[0][n - 1];
}

class Solution {
    public long matrixChain(int[] dims) {
        int n = dims.length - 1;
        long[][] cost = new long[n][n];
        for (int len = 2; len <= n; len++)
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                cost[i][j] = Long.MAX_VALUE;
                for (int k = i; k < j; k++)               // the last split
                    cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k + 1][j] + (long) dims[i] * dims[k + 1] * dims[j + 1]);
            }
        return cost[0][n - 1];
    }
}

function matrixChain(dims) {
  const n = dims.length - 1;
  const cost = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let len = 2; len <= n; len++)
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      cost[i][j] = Infinity;
      for (let k = i; k < j; k++)                       // the last split
        cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]);
    }
  return cost[0][n - 1];
}

fn solve(dims: &[i64]) -> i64 {
    let n = dims.len() - 1;
    let mut cost = vec![vec![0i64; n]; n];
    for len in 2..=n {
        for i in 0..=n - len {
            let j = i + len - 1;
            cost[i][j] = (i..j)                         // k: the last split
                .map(|k| cost[i][k] + cost[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1])
                .min()
                .unwrap();
        }
    }
    cost[0][n - 1]
}

import Data.Array

solve :: [Int] -> Int
solve dims = cost ! (0, n - 1)
  where
    n = length dims - 1
    d = listArray (0, n) dims
    -- a lazy table: every interval refers only to shorter ones
    cost = array ((0, 0), (n - 1, n - 1)) [((i, j), go i j) | i <- [0 .. n - 1], j <- [0 .. n - 1]] :: Array (Int, Int) Int
    go i j
      | i >= j = 0
      | otherwise = minimum [cost ! (i, k) + cost ! (k + 1, j) + d ! i * d ! (k + 1) * d ! (j + 1) | k <- [i .. j - 1]]