Matrix Chain Multiplicaiton

'''
Problem Statement: You will get an array like [2, 1, 3, 4] which represents matrices of dimensions: 2*1,1*3,3*4.
The dimension of multiplying two matrix eg. 2*5 and 5*3 becomes 2*3 and the cost to multiply these two matrix is 2*5*3.
Now, The problem wants to multiply all the matrices of the dimensions one by one with each other but you can decide chain, which two to multiply first so that the overall cost after multyplying all the matrices will be minimum.

Intution: We will break the array, try to find the minimum cost from left matrices and right matrices, then we will multiply the matrices which we got from the left and right and multiply them so total cost will become left matrices minimum cost+ right matrices minimum cost + left and right matrix multiplication cost.

so we will go each matrix one by one in the array and try to break from there, so first matrx will be 0th and ith element of the actual input array so for [2,1,3,4], first matrix will be 2*1 so you can put the first break at 1 where first matrxi will be k-1*k dimension and last break can be at 3 ie. j-1 so last matrix will be 1*3, 3*4 because one matrix is must in both the sides.

once you get the order to multiply the matrices of left and right side, then you want to multiply the overall matrix of left and overall matrix of right, so for a matrix x*y and y*z, cost of multiplication is x*y*z so when you broke the array from k, you are having the overall left array dimension as arr[i]*arr[k], arr[k]*arr[j] so cost of multiplying these two will be arr[i]*arr[k]*arr[j].

Base condition: when there are only two elements in the array, it means only 1 array because two elements represents the one matrix so the cost of multiplying one matrix is 0 or i+1>j means i crossed the j, so doesn't make sense of left to go right side,so return 0.

'''
from math import inf
def fun(arr, i, j, dp):
    # Base condition: If there's only one matrix (or fewer), cost is 0
    # A single matrix is represented by two indices (i, i+1)
    if i + 1 >= j:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]

    temp = inf

    # We split the range (i, j) at index k
    # The split results in two sets of matrices: (i to k) and (k to j)
    for k in range(i + 1, j):
        res = fun(arr, i, k, dp) + fun(arr, k, j, dp) + (arr[i] * arr[k] * arr[j])
        if res < temp:
            temp = res

    dp[i][j] = temp
    return dp[i][j]

class Solution:
    def matrixMultiplication(self, arr):
        # Initialize DP table with -1
        n = len(arr)
        dp = [[-1] * n for _ in range(n)] #This rephresents the minimum number of multiplications needs to be done for arr[i:j]
        return fun(arr, 0, n - 1, dp)