Problem:
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$. Input 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$. Output Print the minimum number of scalar multiplication in a line. Constraints  $1 \leq n \leq 100$  $1 \leq r, c \leq 100$  Sample Input 1 6
30 35
35 15
15 5
5 10
10 20
20 25 Sample Output 1 15125

Solution (Python):
n = int(input())
RC = [list(map(int, input().split())) for _ in range(n)]
R = [RC[i][0] for i in range(n)]
C = [RC[i][1] for i in range(n)]





m = [[10**18]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    m[i][i] = 0
    
for l in range(1, n):
    for i in range(1, n+1-l):
        m[i][i+l] = min([m[i][j] + m[j+1][i+l] + R[i-1]*C[j-1]*C[i+l-1] for j in range(i, i+l)])
        
print(m[1][n])

Solution (Python):
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

n = int(input())
row = []
column = []
for _ in range(n):
    r, c = map(int, input().split())
    row.append(r)
    column.append(c)

dp = [[INF] * (n + 10) for _ in range(n + 10)]

"""
dp[i][j] = iからj番目の行列積に必要なスカラー積の最小値
dp[i][j] = min(dp[i][k] + dp[k+1][j] + M[i].row * M[k].col * M[j].col)
"""

for i in range(n):  
    dp[i][i] = 0

for i in range(n, -1, -1):
    for j in range(i+1, n):
        for k in range(i, j):
            prod = row[i] * column[k] * column[j]
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + prod)
print(dp[0][n-1])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    g = LIR(n)
    dp = [[float("inf")]*(n+1) for i in range(n)]
    for i in range(n):
        dp[i][i+1] = 0
    for k in range(1,n+1):
        for l in range(n):
            hl,wl = g[l]
            r = l+k
            if r > n:
                break
            hr,wr = g[r-1]
            nd = dp[l][r]
            for j in range(l+1,r):
                hj,wj = g[j-1]
                cost = hl*wj*wr
                nd = min(nd,dp[l][j]+dp[j][r]+cost)
            if nd < dp[l][r]:
                dp[l][r] = nd
    print(dp[0][n])
    return


if __name__ == "__main__":
    solve()

Solution (Python):
def s():
 n=int(input())+1
 e=[input().split()for _  in[0]*~-n]
 p=[int(e[0][0])]+list(int(x[1])for x in e)
 m=[[0]*n for _ in[0]*n]
 for i in range(n):
  for r in range(n-i-1):
   c=r+i+1
   for j in range(r+1,c):
    x=m[r][j]+m[j][c]+p[r]*p[j]*p[c]
    if not 0<m[r][c]<=x:m[r][c]=x
 print(m[r][c])
if'__main__'==__name__:s()

Solution (Python):
import sys



N = 100 + 1

p = [0] * N
m = [[0] * N for _ in range(N)]

n = int(input())

for i in range(1, n+1):
    p[i-1], p[i] = map(int, input().split())
for i in range(1, n+1):
    m[i][i] = 0

for l in range(2, n+1):
    for i in range(1, n-l+1+1):
        j = i + l - 1
        m[i][j] = (1 << 21)
        for k in range(i, j-1+1):
            m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j])

print(m[1][n])

Solution (Python):
def main():
    from functools import lru_cache
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(100000000)
    INF=10**9
    n=int(input())
    M=[list(map(int,input().split())) for _ in range(n)]
   
    @lru_cache(maxsize=None)
    def dp(i,j):
        if i+1==j:
            return 0
        else:
            ans=INF
            for k in range(i+1,j):
                ans=min(ans,dp(i,k)+dp(k,j)+M[i][0]*M[k][0]*M[j-1][1])
            return ans
    print(dp(0,n))

if __name__=='__main__':
    main()

Solution (Python):
inf = float('inf')

n = int(input())

r = [0] * n         
c = [0] * n         

for i in range(n):
    ri, ci = map(int, input().split())
    r[i] = ri
    c[i] = ci

dp = [[0]*(n+1) for _ in range(n+1)]  

for ls in range(2, n+1):        
    for i in range(n+1-ls):
        dp[i][i+ls] = inf
        for j in range(i+1, i+ls):  
            dp[i][i+ls] = min(dp[i][i+ls], dp[i][j] + dp[j][i+ls] + r[i]*r[j]*c[i+ls-1])

ans = dp[0][n]

print(ans)

Solution (Python):
MAX = 10 ** 8
n = int(input())
M = [list(map(int,input().split())) for _ in range(n)]
dp = [[MAX for _ in range(n)] for _ in range(n)]
r = [0 for _ in range(n)] 
c = [0 for _ in range(n)] 

for i in range(n):
    r[i] = M[i][0]
    c[i] = M[i][1]
    dp[i][i] = 0

for d in range(1,n):
    for i in range(n-d):
        j = i + d
        min_v = MAX
        for k in range(i,j):
            v = r[i] * c[k] * c[j] + dp[i][k] + dp[k+1][j]
            min_v = min(min_v,v)

        dp[i][j] = min(dp[i][j], min_v)

print (dp[0][n-1])

Solution (Python):
if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    N = 100
    p = [0]*(N+1)
    m = [[0]*(N+1) for _ in range(N+1)]

    n = int(input())
    for i in range(n):
        p[i], p[i+1] = map(int, input().split())

    for l in range(2, n+1):
        for i in range(1, n-l+2):
            j = i + l - 1
            m[i][j] = 2**21 
            for k in range(i, j):
                m[i][j] = min(m[i][j], m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j])

    print(m[1][n])

Solution (Python):
N = int(input())
P = []
for i in range(N):
	ta,tb = map(int ,input().split())
	if i == N-1:
		P.append(ta)
		P.append(tb)
	else:
		P.append(ta)
inf = float('inf')
dp = [[inf] * N for _ in range(N)]
for i in range(N):
	if i == N-1:
		dp[i][i] = 0
	else:
		dp[i][i] = 0
		dp[i][i+1] = P[i]*P[i+1]*P[i+2]

for right in range(2,N):
	for i in range(N):
		j = i + right
		if j > N-1:
			break

		for k in range(i,j):
			dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+P[i]*P[k+1]*P[j+1])

		

print(dp[0][N-1])

Solution (Python):
n = int(input())

M= [[] for i in range(n)]

for i in range(n):
  M[i] = list(map(int, input().split()))

p = [M[0][0]]

for i in range(n):
  p.append(M[i][1])

f_inf = float("inf")

m = [[f_inf for i in range(n)] for j in range(n)]

def matrixChainOrder(n):
  for i in range(n):
    m[i][i] = 0
  for l in range(2, n+1):
    for i in range(n-l+1):
      j = i + l - 1
      for k in range(i, j):
        q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1]
        if q < m[i][j]:
          m[i][j] = q

matrixChainOrder(n)

print(m[0][n-1])

Solution (Python):
def main():
    """連鎖行列積を求める.    
    """
    n = int(input())
    inf = 10**10
    if n == 0 or n == 1:
        print(0)
        return
    if n > 1:
        p = [int(input().split()[0]) for _ in range(n-1)]
    p.extend(list(map(int, input().split())))
    m = [[inf*(i!=j) for i in range(n)] for j in range(n)]
    for l in range(1, n):
        for i in range(n-l):
            j = i+l
            for k in range(i, j):
                m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1])
    print(m[0][-1])

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
for i in range(N):
    if i == 0:
        P = list(map(int, input().split()))
        continue
    P.append(int(input().split()[1]))


INF = 2**32-1
dp = [[INF]*N for _ in range(N)]



for ij in range(N):
    dp[ij][ij] = 0
    
for l in range(1, N):
    for i in range(N-l):
        j = i+l
        for k in range(i,j):
            dp[i][j] = min(dp[i][k] + dp[k+1][j] + P[i]* P[j+1]*P[k+1], dp[i][j])
print(dp[0][-1])

Solution (Python):
class Mychain:
    

    def __init__(self, n):
        self.n = n
        self.lst = [0 for _ in range(n * (n + 1) // 2)]

    def get_index(self, i, j):
        return i - 1 + ((j - i) * (2*self.n - j + i + 1) // 2)

    def get_value(self, i, j):
        return self.lst[self.get_index(i, j)]

    def set_value(self, i, j, value):
        index = self.get_index(i, j)
        self.lst[self.get_index(i, j)] = value


n = int(input())
res = Mychain(n)
matrix = [int(i) for i in input().split()]
matrix.extend([int(input().split()[1]) for i in range(n - 1)])


for n1 in range(1, n + 1):
    for i in range(1, n - n1 + 1):
        j = n1 + i
        value = min(res.get_value(i, i + k) + res.get_value(i + k + 1, j)
                    + matrix[i - 1] * matrix[i + k] * matrix[j]
                    for k in range(n1))
        res.set_value(i, j, value)

print(res.get_value(1, n))

Solution (Python):
def matrix_chain_order(p):
    n = len(p)
    m = {}
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if i == j:
                m[(i, j)] = 0
            else:
                q = None
                for k in range(i, j):
                    c = m[(i, k)] + m[(k+1, j)] + p[i][0] * p[k][1] * p[j][1]
                    if q is None or c < q:
                        q = c
                m[(i, j)] = q
    return m[(0, n-1)]

if __name__ == '__main__':
    import sys

    p = []
    n = int(input())
    for _ in range(n):
        p.append(tuple(map(int, sys.stdin.readline().split())))
    print(matrix_chain_order(p))

Solution (Python):
N = int(input())

for i in range(N):
    if i == 0:
        P = list(map(int, input().split()))  
        continue
    P.append(int(input().split()[1]))



INF = 2**32-1
dp = [[INF]*N for _ in range(N)]



for ij in range(N):
    dp[ij][ij] = 0


for l in range(1, N):  
    for i in range(N):
        j = i+l   
        if j >= N:  
            continue
        for k in range(i, j):  
            dp[i][j] = min(dp[i][k] + dp[k+1][j] + P[i] * P[j+1]*P[k+1], dp[i][j]) 
print(dp[0][-1])

Solution (Python):
def main():
    n = int(input())
    m1 = input().split()
    ps = [int(m1[0]), int(m1[1])]
    for _ in range(n - 1):
        ps.append(int(input().split()[1]))
    ms = [[float("inf") for _ in range(n)] for __ in range(n)]
    
    for i in range(n):
        ms[i][i] = 0

    for length in range(1, n):
        
        
        
        
        
        for start in range(0, n - length):
            end = start + length
            
            m_start_end = float("inf")
            for partition in range(start, end):
                m_start_end = min(m_start_end, ms[start][partition] + ms[partition + 1]
                                  [end] + ps[start] * ps[partition + 1] * ps[end + 1])
            ms[start][end] = m_start_end
    print(ms[0][n - 1])


if __name__ == "__main__":
    main()

Solution (Python):


INF = 2000000000

def matrixChainMultiplication(m):
    global n
    for l in range(2, n+1):
        for i in range(1, n-l + 2):
            j = i + l - 1
            m[i][j] = INF
            for k in range(i, j):
                m[i][j] = min(m[i][j], m[i][k] + m[k+1][j]+p[i-1]*p[k]*p[j])
    return m
 
    
n = int(input())

m = [[0 for i in range(n + 1)] for j in range(n + 1)]
p = []


for i in range(n):
    input_command = input()
    num1,num2 = input_command.split()
    p.append(int(num1))
    if i == n-1:
        p.append(int(num2))
        
m = matrixChainMultiplication(m)
print(m[1][n])

Solution (Python):
import sys


class Mat(object):

  def __init__(self, row, col):
    self.row = row
    self.col = col
    
def get_min_mult_cnt_dp(i, j, mat_list):

  multp = [[sys.maxsize for i in range(len(mat_list))] for i in range(len(mat_list))]

  

  
  for i in range(len(mat_list)):
    multp[i][i] = 0

  for le in range(1, len(mat_list)):
    for i in range(len(mat_list)-le):
      j = i + le

      tmp = sys.maxsize
      for k in range(i, j):
        p = mat_list[i].row
        n = mat_list[k].col
        q = mat_list[j].col
        tmp = multp[i][k] + multp[k+1][j] + p*n*q

        if (tmp < multp[i][j]):
          multp[i][j] = tmp
    
  
  return multp[i][j]
mat_list = []
num = int(input())
for i in range(num):
    a,b = map(int,input().split())
    mat_list.append(Mat(a,b))



print(int(get_min_mult_cnt_dp(0, num-1, mat_list)))

Solution (Python):
def divide_list(l):
    divided_list = [[None, None] for _ in range(len(l) - 1)]
    for i, dl in enumerate(divided_list):
        dl[0], dl[1] = l[0:(i+1)], l[(i+1):]
    return divided_list


def mat_chain_mult(idx_list):
    global a
    global c

    start, end = idx_list[0], idx_list[-1]


    if c[start][end] is not None:
        return c[start][end]

    if len(idx_list) == 1:
        c[start][end] = 0
    elif len(idx_list) == 2:        
        c[start][end] = a[start] * a[start+1] * a[start+2]
    else:
        divided_list = divide_list(idx_list)
        cc = a[start] * a[end+1]
        
        c[start][end] = min([mat_chain_mult(dl0) + mat_chain_mult(dl1) + cc * a[len(dl0) + start] for dl0, dl1 in divided_list])
    
    return c[start][end]
    

if __name__ == "__main__":
    n = int(input())
    a = [0] * (n + 1)
    c = [[None] * n for _ in range(n)]

    for i in range(n-1):
        a[i] = list(map(int, input().split()))[0]
    a[n-1], a[n] = list(map(int, input().split()))

    print(mat_chain_mult(list(range(n))))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def get_cost(l,r):
        if r-l==1:return 0
        if r-l==2:return rc[l][0]*rc[r-1][0]*rc[r-1][1]
        if cost[l][r]!=-1:
            return cost[l][r]
        res=cost[l][r]=min(get_cost(l,m)+get_cost(m,r)
                           +rc[l][0]*rc[m][0]*rc[r-1][1] for m in range(l+1,r))
        return res

    n=int(input())
    rc=[list(map(int,input().split())) for _ in range(n)]
    cost=[[-1]*(n+1) for _ in range(n)]
    print(get_cost(0,n))

main()

Solution (Python):

n = int(input())
p = [None] * (n + 1)
m = [[None for i in range(n+1)] for j in range(n+1)]

for i in range(1, n+1):
    p[i-1], p[i] = map(int, input().split())

for i in range(1, n+1):
    m[i][i] = 0




for l in range(2, n+1):  
    for i in range(1, n-l+2):  
        j = i + l - 1 
        m[i][j] = 1000000000

        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j])

print(m[1][n])

Solution (Python):
def min_cal(A):
    n=len(A)
    ls=[[0 for i in range(n)] for i in range(n)]
    for i in range(n):
        ls[i][i]=0
    for i in range(1,n):
        for j in range(n-i):
            ls[j][i+j]=min([ls[j][k]+ls[k+1][i+j]+A[k][1]*A[j][0]*A[i+j][1] for k in range(j,i+j)])
    return ls[0][n-1]

n=int(input())
Mats=[]
for i in range(n):
    Mats.append([int(i) for i in input().split()])

print(min_cal(Mats))

Solution (Python):
def matrixChainMultiplication(n):
    
    
    for l in range(2, n+1):
        for i in range(1, n-l+1+1):
            j = i + l - 1
            m[i][j] = 999999999
            for k in range(i, j):
                m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j])
    return m[1][n]

n = int(input())
squareM = [input().split(" ") for _ in range(n)]
p = [int(squareM[i][0]) for i in range(n)]
p.append(int(squareM[n-1][1]))
m = [[0]*(n+1) for _ in range(n+1)]
print(matrixChainMultiplication(n))

Solution (Python):
INF = float('inf')


def main():
    n = int(input())
    p = [0 for _ in range(n+1)]

    for i in range(n):
        p1, p2 = map(int, input().split(' '))
        p[i-1], p[i] = p1, p2

    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for l in range(2, n+1):
        for i in range(1, n-l+2):
            j = i + l - 1
            dp[i][j] = INF
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j])
    print(dp[1][n])


if __name__ == "__main__":
    main()

Solution (Python):



import itertools as ite
import math
import random
import sys
import codecs
from collections import defaultdict

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

n = input()
A = map(int, raw_input().split())
for i in range(n - 1):
    n1, n2 = map(int, raw_input().split())
    A += [n2]
DP = [[INF] * n for i in range(n)]
for i in range(n):
    DP[i][i] = 0

for L in range(1, n):
    for i in range(n - L):
        for j in range(L):
            DP[i][i + L] = min(DP[i][i + L], DP[i][i + j] + DP[i + j + 1][i + L] + A[i] * A[i + j + 1] * A[i + L + 1])
print DP[0][n - 1]

Solution (Python):

import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)




n=int(input())
M=[0]*(n+1)
for i in range(n):
    M[i],M[i+1]=map(int,input().split())
dp=[[float('inf')]*n for i in range(n)]
for i in range(n):
    dp[i][i]=0
for k in range(1,n):
    for i in range(n-k):
        j=i+k
        for l in range(i,j):
            dp[i][j]=min(dp[i][j],dp[i][l]+dp[l+1][j]+M[i]*M[l+1]*M[j+1])
print(dp[0][n-1])

Solution (Python):





N = int(input())

for i in range(N):
    if i == 0:
        P = list(map(int, input().split()))
        continue
    P.append(int(input().split()[1]))


INF = 2**32-1
dp = [[INF]*N for _ in range(N)]



for ij in range(N):
    dp[ij][ij] = 0


for l in range(1, N):  
    for i in range(N):
        j = i+l
        if j >= N:
            continue
        for k in range(i, j):
            dp[i][j] = min(dp[i][k] + dp[k+1][j] + P[i]
                           * P[j+1]*P[k+1], dp[i][j])


print(dp[0][-1])

Solution (Python):
def main():
    N = int(input())
    p = []
    for i in range(N):
        r, c = (int(i) for i in input().split())
        p.append(r)
        if i == N - 1:
            p.append(c)
    memo = [[float('inf') for j in range(N + 1)] for i in range(N + 1)]

    def matrix_chain_order():
        for i in range(1,N+1):
            memo[i][i] = 0

        for l in range(2,N+1):
            for i in range(1, N - l + 1 + 1):
                j = i + l - 1
                for k in range(i, j):
                    q = memo[i][k] + memo[k + 1][j] + p[i-1]*p[k]*p[j]
                    if q < memo[i][j]:
                        memo[i][j] = q

    matrix_chain_order()
    print(memo[1][N])

if __name__ == '__main__':
    main()

Solution (Python):
def matrixChainMultiplication():
	INF = 100 * 100 * 100 + 1
	m = [[INF for _ in range(n + 1)] for _ in range(n + 1)]
	for i in range(1, n + 1):
		m[i][i] = 0
	for l in range(2, n + 1):
		for i in range(1, n - l + 2):
			j = i + l - 1
			for k in range(i, j):
				q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]
				if q < m[i][j]:
					m[i][j] = q
	return m[1][n]

if __name__ == "__main__":
	n = int(input())
	p = list(map(int, input().split()))
	for i in range(1, n):
		p.append(list(map(int, input().split()))[1])
	print(matrixChainMultiplication())

Solution (Python):
import sys
input = sys.stdin.readline
INF = 1001001001001001
def main():
    n = int(input())
    p = [0] * (n+1)
    for i in range(n):
        p[i], p[i+1] = map(int, input().split())
    dp = [[INF]*(n+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][i] = 0
    for l in range(2, n+1):
        for i in range(n-l+2):
            j = i + l - 1
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j])
    print(dp[1][n])
if __name__ == '__main__': main()

Solution (Python):
import sys

n = int(input())
m = []
for i in range(n):
    inpt = list(map(int, input().split( )))
    m.append(inpt)

lrg = 1000000
DP = [[lrg for i in range(n)] for j in range(n)]


for i in range(n):
    DP[i][i] = 0

if n >= 1:
    for i in range(n-1):
        DP[i][i+1] = m[i][0]*m[i][1]*m[i+1][1]

for d in range(2,n):
    for i in range(n-d):
        for j in range(i+1,i+d):
            DP[i][i+d] = min(DP[i][i+d],DP[i][j]+DP[j+1][i+d]+m[i][0]*m[j][1]*m[i+d][1])

    
print(DP[0][n-1])

Solution (Python):
import sys


def getmin(i, j, mlist, memo={}):
    if i == j:
        return 0
    elif (i, j) in memo:
        return memo[(i, j)]
    else:
        ret = sys.maxsize
        for k in range(i, j):
            p = mlist[i][0]
            n = mlist[k][1]
            q = mlist[j][1]
            tmp = getmin(i, k, mlist, memo) + \
                getmin(k+1, j, mlist, memo) + p*n*q

            if tmp < ret:
                ret = tmp

        memo[(i, j)] = ret
        return memo[(i, j)]


def main():
    n = int(input())
    M = [[0, 0] for i in range(n)]
    for i in range(n):
        M[i] = list(map(int, input().split()))

    print(getmin(0, n-1, M))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    p = [0] * (n + 1)
    m = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n):
        p[i], p[i + 1] = map(int, input().split())
    for l in range(2, n + 1):
        for i in range(1, n - l + 2):
            j = i + l - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                p_prod = p[i - 1] * p[k] * p[j]
                m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p_prod)
    print(m[1][n])


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
r=[0]*(n+1)
c=[0]*(n+1)
for i in range(n):
    r[i+1], c[i+1] = map(int, input().split())

dp = [[float('inf') for i in range(n+1)] for j in range(n+1)]

for i in range(n+1):
    dp[i][i] = 0


for l in range(2, n+1):
    for i in range(1, n-l+2):
        
        tmp_list = [r[i] * c[i+l-1] * r[j+1] + dp[i][j] + dp[j+1][i+l-1] for j in range(i, i+l-1)]
        dp[i][i+l-1] = min(tmp_list)

print(dp[1][n])

Solution (Python):
import sys
from typing import List


if __name__ == "__main__":
    num_matrix = int(input())
    matrices: List[List[int]] = []
    for _ in range(num_matrix):
        matrices.append(list(map(lambda x: int(x), input().split())))
    dp = [[sys.maxsize] * num_matrix for i in range(num_matrix)]
    for i in range(num_matrix):
        dp[i][i] = 0

    for l in range(1, num_matrix):
        for i in range(num_matrix - l):
            row = matrices[i][0]
            col = matrices[i + l][1]
            dp[i][i + l] = min(row * matrices[j][1] * col + dp[i][j] + dp[j + 1][i + l]
                               for j in range(i, i + l))

    print(f"{dp[0][num_matrix - 1]}")

Solution (Python):

INF = 10**9

if __name__ == '__main__':
    n = int(raw_input())

    
    
    
    
    
    
    
    dp = [[0 for j in range(n+1)] for i in range(n+1)]  
    p = [0 for i in range(n+1)]  
    for i in range(1, n+1):
        p[i-1], p[i] = map(int, raw_input().split())

    
    for i in range(1, n+1):
        dp[i][i] = 0

    
    for l in range(2, n+1):
        
        
        for i in range(1, n-l+1+1):
            j = l+i-1
            minv = INF
            for k in range(i, j):
                
                
                
                minv = min(minv, dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j])
            dp[i][j] = minv
    print dp[1][n]

Solution (Python):
import sys
input = sys.stdin.readline
a = []
dp = []


def rec(l, r):
	if dp[l][r] != -1:
		return dp[l][r]
	if l+1 == r:
		dp[l][r] = 0
		return dp[l][r]
	if l+2 == r:
		dp[l][r] = a[l][0] * a[l][1] * a[l+1][1]
		return dp[l][r]

	m = 100000000
	for i in range(l+1, r):
		m = min(m, rec(l, i) + rec(i, r) + a[l][0] * a[i][0] * a[r-1][1])
	dp[l][r] = m
	return dp[l][r]

def main():
	global a, dp
	n = int(input().strip())
	for i in range(n):
		a.append(tuple(map(int, input().strip().split())))
	dp = [[-1] * (n+1) for _ in range(n)]
	print(rec(0, n))

if __name__ == '__main__':
	main()

Solution (Python):
INFTY = 100 * 100 * 100 + 1  


n = int(input())

p = [None for _ in range(n + 1)]
m = [[None] * (n + 1) for _ in range(n + 1)]

for i in range(n):
    r, c = map(int, input().split())

    if i == 0:
        p[0] = r

    p[i + 1] = c

def matrix_chain_multiplication():
    for i in range(1, n + 1):
        m[i][i] = 0

    for l in range(2, n + 1):
        for i in range(1, n - l + 1 + 1):
            j = i + l - 1
            m[i][j] = INFTY
            for k in range(i, j - 1 + 1):
                m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j])


matrix_chain_multiplication()
print(m[1][n])

Solution (Python):
n = int(input())
M = []
for _ in range(n):
    M.append([int(i) for i in input().split()])

def martixChainMultipication(M):
    n = len(M)
    m = [[0 for _ in range(n)] for _ in range(n)]
    for l in range(2, n+1):
        for i in range(1, n-l+2):
            j = i + l - 1
            m[i-1][j-1] = 1000000
            for k in range(i, j):
                cost = m[i-1][k-1]+m[k][j-1]+M[i-1][0]*M[k-1][1]*M[j-1][1]
                m[i-1][j-1] = min(m[i-1][j-1], cost)
    return m

print(martixChainMultipication(M)[0][n-1])

Solution (Python):
import sys


input = sys.stdin.readline
n = int(input())
m_list = []
for _ in range(n):
    m_list.append(list(map(int, input().split())))

p_list = [m_list[0][0]]
for i in range(n):
    p_list.append(m_list[i][1])

m = [[10**9]*(n+1) for i in range(n+1)]

for i in range(1, n+1):
    m[i][i] = 0
for l in range(2, n+1):
    for i in range(1, n-l+2):
        j = i + l - 1
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k]+m[k+1][j]+p_list[i-1]*p_list[k]*p_list[j])

print(m[1][n])

Solution (Python):
n = int(input())
A = [list(map(int, input().split())) for i in range(n)]

ans = [[None for i in range(n)] for j in range(n)]



def dp1(i, j):
    if ans[i][j] is not None:
        return ans[i][j]
    else:
        if i == j:
            ans[i][j] = 0
        else:
            ret = float('INF')
            for k in range(i, j):
                tmp = dp1(i, k) + A[i][0]*A[k][1]*A[j][1] + dp1(k+1, j)
                ret = min(ret, tmp)
            ans[i][j] = ret
        return ans[i][j]


print(dp1(0, n-1))

Solution (Python):
n = int(input())
rc = [[0, 0]]+[list(map(int, input().split())) for i in range(n)]
m = [[0]*(n+1) for _ in range(n+1)]

for l in range(2, n+1):
    for i in range(1, n-l+2):
        j = i+l-1
        m[i][j] = 2**64
        for k in range(i, j):
            m[i][j] = min([
                m[i][j],
                m[i][k]+m[k+1][j]+rc[i][0]*rc[k+1][0]*rc[j][1]
            ])
print(m[1][n])

Solution (Python):

"""
Created on Fri Mar 22 14:15:50 2019

@author: Yamazaki Kenichi
"""

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
B = [A[0][0]]
for c in A:
    B += [c[1]]

T = [[0 for i in range(n)] for i in range(n)]
for i in range(1,n):
    for j in range(n-i):
        if i == 1:
            T[i][j] = B[j]*B[j+1]*B[j+2]
            continue
        temp = 10**6
        for k in range(1,i+1):
             temp = min(temp,
                        T[i-k][j] + T[k-1][j+(i-k)+1] + B[j]*B[j+i-k+1]*B[j+i+1])
        T[i][j] = temp
print(T[n-1][0])

Solution (Python):


INF = 1 << 60
n = int(input().rstrip())
r = [0 for _ in range(n+10)]
c = [0 for _ in range(n+10)]

dp = [[INF for _ in range(n+10)] for _ in range(n+10)]
for i in range(n):
    line = input().rstrip().split()
    r[i] = int(line[0])
    c[i] = int(line[1])
    
for i in range(n):
    dp[i][i] = 0


for l in range(1,n):
    for i in range(n - l):
        j = i + l
        for k in range(i,j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + r[i]*c[k]*c[j])
            
print(dp[0][n-1])

Solution (Python):
import math

n = int(input())
dp = [[0 for j in range(n+1)] for i in range(n+1)]
p = []

def init(p):
    global dp
    for i in range(1, n):
        dp[i][i+1] = p[i-1]*p[i]*p[i+1]

def solve(r, c):
    global dp
    smallest = math.inf
    for i in range(r, c):
        temp = p[r-1]*p[i]*p[c] + dp[r][i] + dp[i+1][c]
        if temp < smallest:
            smallest = temp
    return smallest

first = list(map(int,input().split()))
p.append(first[0])
p.append(first[1])
for i in range(n-1):
    temp = list(map(int,input().split()))
    p.append(temp[1])

init(p)
for j in range(3, n+1):
    for i in range(j-2, 0, -1):
        dp[i][j] = solve(i, j)
print(str(dp[1][n]))

Solution (Python):
n = int(input())
M = []
dp = [[None for i in range(100)] for i in range(100)]

def calcMatrix(i,j):
    
    if i == j:
        dp[i][j] = 0
    elif i == j-1:
        dp[i][j] = M[i]*M[i+1]*M[i+2]
    else:
        for k in range(j-i):
            
            
            
            
            current = dp[i][i+k] + dp[i+k+1][j] + M[i]*M[i+k+1]*M[j+1]
            if k==0:
                dp[i][j] = current
            if current < dp[i][j]:
                dp[i][j] = current 

for i in range(n-1):
    Q = list(map(int,input().split()))
    M.append(Q[0])
Q = list(map(int,input().split()))
M.append(Q[0])
M.append(Q[1])


for i in range(n):
    for j in range(n-i):
        calcMatrix(j,i+j)
        
        
        
print(dp[0][n-1])

Solution (Python):
n = int(input())
data = list(list(map(int, input().split())) for _ in range(n))
m = [[None for _ in range(n+1)]for _ in range(n+1)]
p = []
INF = 1000000000

for i in range(1, n+1):
    m[i][i] = 0

p.append(data[0][0])
for i in range(n):
    p.append(data[i][1])

for l in range(2, n+1):
    for i in range(1, n - l + 2):
        j = i + l - 1
        m[i][j] = INF
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j])



print(m[1][n])

Solution (Python):
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):
                    
                    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]
        
    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))

Solution (Python):

def mcm(p,n):
	m=[[0 for x in range(n+1)] for x in range(n+1)]
	for s in range(n):
		for i,j in zip(range(1,n+1),range(s+2,n+1)):
			m[i][j] = 1 << 30
			for k in range(i,j):
				m[i][j]=min(m[i][j],m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j])
	return m[1][n]

n=int(input())
p=[0]*(n+1)
for i in range(n-1):
	t=list(map(int,input().split()))
	p[i]=t[0];
t=list(map(int,input().split()))
p[n-1]=t[0]
p[n]=t[1]

ans=mcm(p,n)
print(ans)