Can use the matrix chain multiplication algorithm
Solved step by step with explanation optimum number of multiplications performed using dynamic programming
Question
Answer
Solved step by step with explanation optimum number of multiplications performed using dynamic programming
The table will have dimensions (n-1) X (n-1), where n is the number of matrices (in this case, 4).
Initialize all values in the table as infinity (or a very large number).
After completing all iterations, the top-right cell of the table will contain the minimum number of multiplications required for multiplying all matrices.
In this case, the value in the top-right cell will be the answer, which is 6500.
def matrix_chain_multiplication(dims):
n = len(dims) - 1 # Number of matrices
# Chain length iteration
for chain_length in range(2, n + 1):
cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1]
if cost < dp[i][j]:
optimum_multiplications = matrix_chain_multiplication(matrix_dimensions)
print("Optimum number of multiplications:", optimum_multiplications)
