MatrixChainMultiplication.py

import sys


memo = [[None for _ in range(1001)] for _ in range(1001)]


def MatrixChainMultiplicationRec(array, i, j):
    if i == j:
        return 0
    minn = sys.maxsize

    for k in range(i, j):
        count = (
            MatrixChainMultiplicationRec(array, i, k)
            + MatrixChainMultiplicationRec(array, k + 1, j)
            + (array[i - 1] * array[k] * array[j])
        )
        minn = min(minn, count)

    return minn


def MatrixChainMultiplicationMemo(array, i, j):
    if i == j:
        return 0
    if memo[i][j] is not None:
        return memo[i][j]

    minn = sys.maxsize

    for k in range(i, j):
        count = (
            MatrixChainMultiplicationMemo(array, i, k)
            + MatrixChainMultiplicationMemo(array, k + 1, j)
            + (array[i - 1] * array[k] * array[j])
        )
        minn = min(minn, count)
    memo[i][j] = minn
    return memo[i][j]


def MatrixChainMultiplicationDp(array, n):
    """ n is length of array """
    dp = [[None for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        for j in range(n + 1):
            if i == j:
                dp[i][j] = 0
            else:
                dp[i][j] = sys.maxsize
                for k in range(i + 1, j):
                    count = (
                        dp[i][k] + dp[k + 1][j] + (array[i - 1] * array[k] * array[j])
                    )
                    dp[i][j] = min(count, dp[i][j])

    return dp[n][n]


def main():
    array = [1, 2, 3, 4, 3]
    print(MatrixChainMultiplicationRec(array, 1, len(array) - 1))
    print(MatrixChainMultiplicationMemo(array, 1, len(array) - 1))
    print(MatrixChainMultiplicationDp(array, len(array)))


if __name__ == "__main__":
    main()