Python program to solve matrix-chain multiplication

An assignment at school required me to write a program for this task:

In the matrix-chain multiplication problem, we are given a sequence of matrices A(1), A(2), …, A(n). The aim is to compute the product A(1) …, A(n) with the minimum number of scalar multiplications. Thus, we have to find an optimal parenthesization of the matrix product A(1) …, A(n) such that the cost of computing the product is minimized.

Here is my solution to this task (in Python):

def matrix_product(p):     """     Return m and s.      m[i][j] is the minimum number of scalar multiplications needed to compute the     product of matrices A(i), A(i + 1), ..., A(j).      s[i][j] is the index of the matrix after which the product is split in an     optimal parenthesization of the matrix product.      p[0... n] is a list such that matrix A(i) has dimensions p[i - 1] x p[i].     """     length = len(p) # len(p) = number of matrices + 1      # m[i][j] is the minimum number of multiplications needed to compute the     # product of matrices A(i), A(i+1), ..., A(j)     # s[i][j] is the matrix after which the product is split in the minimum     # number of multiplications needed     m = [[-1]*length for _ in range(length)]     s = [[-1]*length for _ in range(length)]      matrix_product_helper(p, 1, length - 1, m, s)      return m, s   def matrix_product_helper(p, start, end, m, s):      """     Return the minimum number of scalar multiplications needed to compute the     product of matrices A(start), A(start + 1), ..., A(end).      The minimum number of scalar multiplications needed to compute the     product of matrices A(i), A(i + 1), ..., A(j) is stored in m[i][j].      The index of the matrix after which the above product is split in an optimal     parenthesization is stored in s[i][j].      p[0... n] is a list such that matrix A(i) has dimensions p[i - 1] x p[i].     """     if m[start][end] >= 0:         return m[start][end]      if start == end:         q = 0     else:         q = float('inf')         for k in range(start, end):             temp = matrix_product_helper(p, start, k, m, s) \                    + matrix_product_helper(p, k + 1, end, m, s) \                    + p[start - 1]*p[k]*p[end]             if q > temp:                 q = temp                 s[start][end] = k      m[start][end] = q     return q   def print_parenthesization(s, start, end):     """     Print the optimal parenthesization of the matrix product A(start) x     A(start + 1) x ... x A(end).      s[i][j] is the index of the matrix after which the product is split in an     optimal parenthesization of the matrix product.     """     if start == end:         print('A[{}]'.format(start), end='')         return      k = s[start][end]      print('(', end='')     print_parenthesization(s, start, k)     print_parenthesization(s, k + 1, end)     print(')', end='')   n = int(input('Enter number of matrices: ')) p = [] for i in range(n):     temp = int(input('Enter number of rows in matrix {}: '.format(i + 1)))     p.append(temp) temp = int(input('Enter number of columns in matrix {}: '.format(n))) p.append(temp)  m, s = matrix_product(p) print('The number of scalar multiplications needed:', m[1][n]) print('Optimal parenthesization: ', end='') print_parenthesization(s, 1, n) 

Here is an example output:

Enter number of matrices: 3 Enter number of rows in matrix 1: 10 Enter number of rows in matrix 2: 100 Enter number of rows in matrix 3: 5 Enter number of columns in matrix 3: 50 The number of scalar multiplications needed: 7500 Optimal parenthesization: ((A[1]A[2])A[3]) 

NOTE – The time taken for print_parenthesization() (for this example) is 0:00:15.332220 seconds.

So, I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.