find the minimum number of multiplications needed to multiply chain of matrices reference https www geeksforgeeks orgmatrixchainmultiplicationdp8 the algorithm has interesting realworld applications example 1 image transformations in computer graphics as images are composed of matrix 2 solve complex polynomial equations in the field of algebra using least processing power 3 calculate overall impact of macroeconomic decisions as economic equations involve a number of variables 4 selfdriving car navigation can be made more accurate as matrix multiplication can accurately determine position and orientation of obstacles in short time python doctests can be run with the following command python m doctest v matrixchainmultiply py given a sequence arr that represents chain of 2d matrices such that the dimension of the ith matrix is arri1arri so suppose arr 40 20 30 10 30 means we have 4 matrices of dimensions 4020 2030 3010 and 1030 matrixchainmultiply returns an integer denoting minimum number of multiplications to multiply the chain we do not need to perform actual multiplication here we only need to decide the order in which to perform the multiplication hints 1 number of multiplications ie cost to multiply 2 matrices of size mp and pn is mpn 2 cost of matrix multiplication is associative ie m1m2m3 m1m2m3 3 matrix multiplication is not commutative so m1m2 does not mean m2m1 can be done 4 to determine the required order we can try different combinations so this problem has overlapping subproblems and can be solved using recursion we use dynamic programming for optimal time complexity example input arr 40 20 30 10 30 output 26000 find the minimum number of multiplcations required to multiply the chain of matrices args arr the input array of integers returns minimum number of multiplications needed to multiply the chain examples matrixchainmultiply1 2 3 4 3 30 matrixchainmultiply10 0 matrixchainmultiply10 20 0 matrixchainmultiply19 2 19 722 matrixchainmultiplylistrange1 100 323398 matrixchainmultiplylistrange1 251 2626798 initialising 2d dp matrix we want minimum cost of multiplication of matrices of dimension ik and kj this cost is arri1arrkarrj source https en wikipedia orgwikimatrixchainmultiplication the dynamic programming solution is faster than cached the recursive solution and can handle larger inputs matrixchainorder1 2 3 4 3 30 matrixchainorder10 0 matrixchainorder10 20 0 matrixchainorder19 2 19 722 matrixchainorderlistrange1 100 323398 matrixchainorderlistrange1 251 max before recursionerror is raised 2626798 printfstarting msg find the minimum number of multiplcations required to multiply the chain of matrices args arr the input array of integers returns minimum number of multiplications needed to multiply the chain examples matrix_chain_multiply 1 2 3 4 3 30 matrix_chain_multiply 10 0 matrix_chain_multiply 10 20 0 matrix_chain_multiply 19 2 19 722 matrix_chain_multiply list range 1 100 323398 matrix_chain_multiply list range 1 251 2626798 initialising 2d dp matrix we want minimum cost of multiplication of matrices of dimension i k and k j this cost is arr i 1 arr k arr j source https en wikipedia org wiki matrix_chain_multiplication the dynamic programming solution is faster than cached the recursive solution and can handle larger inputs matrix_chain_order 1 2 3 4 3 30 matrix_chain_order 10 0 matrix_chain_order 10 20 0 matrix_chain_order 19 2 19 722 matrix_chain_order list range 1 100 323398 matrix_chain_order list range 1 251 max before recursionerror is raised 2626798 print f starting msg
from collections.abc import Iterator
from contextlib import contextmanager
from functools import cache
from sys import maxsize


def matrix_chain_multiply(arr: list[int]) -> int:
    
    if len(arr) < 2:
        return 0
    
    n = len(arr)
    dp = [[maxsize for j in range(n)] for i in range(n)]
    
    
    for i in range(n - 1, 0, -1):
        for j in range(i, n):
            if i == j:
                dp[i][j] = 0
                continue
            for k in range(i, j):
                dp[i][j] = min(
                    dp[i][j], dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
                )

    return dp[1][n - 1]


def matrix_chain_order(dims: list[int]) -> int:
    

    @cache
    def a(i: int, j: int) -> int:
        return min(
            (a(i, k) + dims[i] * dims[k] * dims[j] + a(k, j) for k in range(i + 1, j)),
            default=0,
        )

    return a(0, len(dims) - 1)


@contextmanager
def elapsed_time(msg: str) -> Iterator:
    
    from time import perf_counter_ns

    start = perf_counter_ns()
    yield
    print(f"Finished: {msg} in {(perf_counter_ns() - start) / 10 ** 9} seconds.")


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    with elapsed_time("matrix_chain_order"):
        print(f"{matrix_chain_order(list(range(1, 251))) = }")
    with elapsed_time("matrix_chain_multiply"):
        print(f"{matrix_chain_multiply(list(range(1, 251))) = }")
    with elapsed_time("matrix_chain_order"):
        print(f"{matrix_chain_order(list(range(1, 251))) = }")
    with elapsed_time("matrix_chain_multiply"):
        print(f"{matrix_chain_multiply(list(range(1, 251))) = }")