Algorithms: Dynamic Programming

def matrix_chain(dimensions: list[int]) -> int:
    alg_require(isinstance(dimensions, (list, tuple)) and len(dimensions) <= 1000000)
    n: int = len(dimensions) - 1
    alg_require(n >= 0 and n <= 1000000)
    alg_require(len(dimensions) == n + 1)
    alg_require(n >= 1)
    for value in dimensions:
        alg_require(value > 0 and value <= 1000)
    dp: list[int] = [0] * alg_size(n * n)
    length: int = 2
    left: int = 0
    right: int = 0

int matrix_chain(const int *dimensions, size_t dimensions_length) {
    int alg_error = 0;
    int alg_result = INT_MIN;
    errno = 0;
    int *dp = NULL;
    if (dimensions_length > 1000000 || (dimensions_length && !dimensions)) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    int n = alg_sub((int)dimensions_length, 1, &alg_error);
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((n >= 0) && (n <= 1000000)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((int)dimensions_length == alg_add(n, 1, &alg_error)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }

int matrix_chain(const std::vector<int>& dimensions) {
    alg_require(dimensions.size() <= 1000000);
    int n = alg_sub((int)dimensions.size(), 1);
    alg_require(((n >= 0) && (n <= 1000000)));
    alg_require(((int)dimensions.size() == alg_add(n, 1)));
    alg_require((n >= 1));
    for (int alg_i = 0; alg_i < (int)dimensions.size(); alg_i++) {
        int alg_value = dimensions[alg_i];
        alg_require(((alg_value > 0) && (alg_value <= 1000)));
    }
    std::vector<int> dp(alg_size(alg_mul(n, n)), 0);
    int length = 2;

    static int matrix_chain(ReadOnlySpan<int> dimensions) {
        checked {
            int n = (dimensions.Length - 1);
            alg_require(((n >= 0) && (n <= 1000000)));
            alg_require((dimensions.Length == (n + 1)));
            alg_require((n >= 1));
            for (int alg_i = 0; alg_i < dimensions.Length; alg_i++) {
                int alg_value = dimensions[alg_i];
                alg_require(((alg_value > 0) && (alg_value <= 1000)));
            }
            int[] dp = new int[alg_size((n * n))];
            int length = 2;

function matrix_chain(array $dimensions): int {
    alg_require(array_is_list($dimensions));
    $n = alg_sub(count($dimensions), 1);
    alg_require((($n >= 0) && ($n <= 1000000)));
    alg_require((count($dimensions) == alg_add($n, 1)));
    alg_require(($n >= 1));
    for ($alg_i = 0; $alg_i < count($dimensions); $alg_i++) {
        $alg_value = $dimensions[$alg_i];
        alg_require((($alg_value > 0) && ($alg_value <= 1000)));
    }
    $dp = array_fill(0, alg_size(alg_mul($n, $n)), 0);
    $length = 2;