output_description: Print the minimum number of scalar multiplication in a line.
input_description: In the first line, an integer $n$ is given. In the following $n$ lines, the
  dimension of matrix $M_i$ ($i = 1...n$) is given by two integers $r$ and $c$
  which respectively represents the number of rows and columns of $M_i$.
attempt: def matrix_chmul(matrices):
      length = len(matrices)
      dp = [[0 for n in range(length)] for m in range(length)]
      rowcol = []
      for i in range(length):
          rowcol.extend(matrices[i])
      for i in range(1, length):
          for j in range(length - i):
              if i == 1:
                  dp[j][i + j] = (
                      rowcol[j * 2] * rowcol[(i + j) * 2] * rowcol[(i + j) * 2 + 1]
                  )
              else:
                  temp_min = float("inf")
                  for k in range(0, i):
                      # print(i, j, k, dp[j][j + k], dp[j + k + 1][i + j])
                      dp[j][i + j] = min(
                          temp_min,
                          (
                              dp[j][j + k]
                              + dp[j + k + 1][i + j]
                              + rowcol[j * 2]
                              * rowcol[(j + k + 1) * 2]
                              * rowcol[(i + j) * 2 + 1]
                          ),
                      )
                      temp_min = dp[j][i + j]
          # print(dp)
      return dp[0][length - 1]
  
  
  length = int(input())
  matrices = [[0 for n in range(2)] for m in range(length)]
  for _ in range(length):
      x, y = [int(n) for n in input().split(" ")]
      matrices[_] = x, y
  print(matrix_chmul(matrices))
  
problem_description: Matrix-chain Multiplication
  
  The goal of the matrix-chain multiplication problem is to find the most
  efficient way to multiply given $n$ matrices $M_1, M_2, M_3,...,M_n$.
  
  Write a program which reads dimensions of $M_i$, and finds the minimum number
  of scalar multiplications to compute the maxrix-chain multiplication
  $M_1M_2...M_n$.
samples: [{"input": "6\n    30 35\n    35 15\n    15 5\n    5 10\n    10 20\n    20 25", "output": "15125"}]