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())
p = [item for sublist in [[int(input().split()[1])] if i != 0 else list(map(int, input().split())) for i in range(n)] for item in sublist]

def memolize(f):
    cache = {}

    def helper(x, y):
        if (x, y) not in cache:
            cache[(x, y)] = f(x, y)
        return cache[(x, y)]
    return helper

@memolize
def calcMatrixOrder(i, j):
    if i == j :
        return 0
    return min([calcMatrixOrder(i, k) + calcMatrixOrder(k + 1, j) + p[i]*p[k+1]*p[j + 1] for k in range(i, j)])

print(calcMatrixOrder(0, n - 1))

Solution (Python):
n = int(input())
p = [item for sublist in [[int(input().split()[1])] if i != 0 else list(map(int, input().split())) for i in range(n)] for item in sublist]

def memolize(f):
    cache = {}

    def helper(x, y):
        if (x, y) not in cache:
            cache[(x, y)] = f(x, y)
        return cache[(x, y)]
    return helper

@memolize
def calcMatrixOrder(i, j):
    if i == j :
        return 0
    return min([calcMatrixOrder(i, k) + calcMatrixOrder(k + 1, j) + p[i]*p[k+1]*p[j + 1] for k in range(i, j)])

print(calcMatrixOrder(0, n - 1))

Solution (Python):
import sys

def get_min_cost(n, p):
	m = [[0 for x in range(n+1)] for x in range(n+1)]
	for s in range(n):
		i = 1
		for j in range(s+2, n+1):
			m[i][j] = sys.maxsize
			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])
			i+=1	
	return m[1][n]

n = int(input())
p = [0] * (n+1)
j = 0
for i in range(n):
	a = list(map(int, input().split()))
	if i == 0:
		p[j] = a[0]
		j += 1
	p[j] = a[1]
	j += 1
print(get_min_cost(n, p))

Solution (Python):
import sys

n = int(sys.stdin.readline())

m = list(map(int, sys.stdin.readline().split()))
for _ in range(n-1):
    _, a = sys.stdin.readline().split()
    m.append(int(a))

c = [[-1 for _ in range(n)] for _ in range(n)]

def val(a, b):
    if a==b: return 0
    if c[a][b]>0: return c[a][b]
    c[a][b]=val(a+1,b)+m[a-1]*m[a]*m[b]
    for k in range(a+1, b):
        v=val(a,k)+val(k+1,b)+m[a-1]*m[k]*m[b]
        if c[a][b]>v: c[a][b]=v
    return c[a][b]

print(val(0, n-1))

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

N=INT()
P=[0]*(N+1)
for i in range(N):
    r,c=MAP()
    if i==0:
        P[i]=r
    P[i+1]=c

dp=[[INF]*(N+1) for i 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):
        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])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)








def solve():
    n = int(input())
    mat_list = []
    for i in range(n):
        mat_list.append(list(map(int, input().split())))
    dprint(mat_list)

    
    memo = [[0 for i in range(n)] for i in range(n)]

    def calc(start, end):
        dprint("*", start, end)
        
        if end == start:
            return 0

        
        if memo[start][end] != 0:
            return memo[start][end]

        
        if end - start == 1:
            cost = mat_list[start][0] * mat_list[start][1] * mat_list[end][1]
            memo[start][end] = cost
            dprint(start, end, cost)
            return cost

        
        min_cost = -1
        if end - start >= 2:
            for right_start in range(start+1, end+1):
                left = calc(start, right_start-1)
                right = calc(right_start, end)
                cost = left + right + mat_list[start][0] * mat_list[right_start][0] * mat_list[end][1]
                if min_cost == -1 or min_cost > cost:
                    min_cost = cost
                dprint(start, end, right_start, min_cost, cost)

        memo[start][end] = min_cost
        return min_cost

    ans = calc(0, n-1)
    dprint(memo)
    print(int(ans))

solve()

Solution (Python):
N = input()
M = [map(int, raw_input().split()) for i in xrange(N)]
cache = {}
for i in xrange(N):
    cache[(i, i+1)] = 0
def dfs(left, right):
    if (left, right) in cache:
        return cache[(left, right)]
    min_cost = float("inf")
    for mid in xrange(left+1, right):
        tmp = M[left][0] * M[mid-1][1] * M[right-1][1]
        tmp += dfs(left, mid)
        tmp += dfs(mid, right)
        if min_cost > tmp:
            min_cost = tmp
    cache[(left, right)] = min_cost
    return min_cost
print dfs(0, len(M))

Solution (Python):
def memoize(f):  
    cache = {}  
    def helper(x):  
        if x not in cache:              
            cache[x] = f(x)  
        return cache[x]  
    return helper 

def split_rc(rc):
    for i in range(1, len(rc)):
        yield rc[:i], rc[i:]

@memoize
def cost(rc):
    if len(rc) == 1:
        return 0
    return min(calc_cost(first, second) for first, second in split_rc(rc))

def calc_cost(first, second):
    return cost(first) + cost(second) + first[0][0] * first[-1][1] * second[-1][1]

n = int(input())
rc = tuple(tuple(map(int, input().split())) for _ in range(n))
print(cost(rc))

Solution (Python):
N = input()
M = [map(int, raw_input().split()) for i in xrange(N)]
cache = {}
for i in xrange(N):
    cache[(i, i+1)] = 0
def dfs(left, right):
    if (left, right) in cache:
        return cache[(left, right)]
    min_cost = float("inf")
    for mid in xrange(left+1, right):
        tmp = M[left][0] * M[mid-1][1] * M[right-1][1]
        tmp += dfs(left, mid)
        tmp += dfs(mid, right)
        if min_cost > tmp:
            min_cost = tmp
    cache[(left, right)] = min_cost
    return min_cost
print dfs(0, len(M))

Solution (Python):
import sys

p=[0 for i in range (101)]
m=[[0 for i in range(100)]for i in range(100)]

def MatrixChain(n) : 
	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] = float('Infinity')
			for k in range(i,j) :
				q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
				m[i][j] = m[i][j] if m[i][j] <= q else q

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

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

Solution (Python):

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


best = [[float('inf') for j in range(n)] for i in range(n)]
for j in range(0, n):
    for i in range(n - j):
        l = []
        for k in range(j):
            c1 = best[i][i + k]
            c2 = best[i + k + 1][i + j]
            c3 = M[i][0] * M[i + k][1]  * M[i + j][1]
            l.append(c1 + c2 + c3)
        best[i][i + j] = 0 if len(l) == 0 else min(l)
print(best[0][n-1])

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

def update(i,l,n,ms,dp):
    min_val = 10000000000000
    for k in range(1,l):
        val = dp[i][k]+dp[i+k][l-k]+ms[i][0]*ms[i+k-1][1]*ms[i+l-1][1]
        if min_val > val:
            min_val = val
    return min_val

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

ms = []
for i in range(n):
    r,c = map(int, raw_input().split(' '))
    ms.append((r,c))

for l in range(2,n+1):
    for i in range(n):
        if i + l > n: break
        dp[i][l] = update(i,l,n,ms,dp)

print dp[0][n]

Solution (Python):
def solve(a):
    n = len(a)
    cost = [[0 for i in range(n)] for j in range(n)]
 
    for length in range(2, n+1):
        for i in range(0, n-length+1):
            k = i+length-1
            def f(i,j,k):
                return cost[i][j-1]+cost[j][k]+M[i][0]*M[j-1][1]*M[k][1]
            cost[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
    return cost[0][n-1]
 
n = input()
M = []
for i in range(n):
    M.append(map(int, raw_input().split()))
print solve(M)

Solution (Python):
def solve(a):
    n = len(a)
    cost = [[0 for i in range(n)] for j in range(n)]
 
    for length in range(2, n+1):
        for i in range(0, n-length+1):
            k = i+length-1
            def f(i,j,k):
                return cost[i][j-1]+cost[j][k]+M[i][0]*M[j-1][1]*M[k][1]
            cost[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
    return cost[0][n-1]
n = input()
M = []
for i in range(n):
    M.append(map(int, raw_input().split()))
print solve(M)

Solution (Python):
def solve(a):
 n = len(a)
 cost = [[0 for i in range(n)] for j in range(n)]
 for length in range(2, n+1):
  for i in range(0, n-length+1):
   k = i+length-1
   def f(i,j,k):
    return cost[i][j-1]+cost[j][k]+M[i][0]*M[j-1][1]*M[k][1]
   cost[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
 return cost[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print solve(M)

Solution (Python):
def solve(a):
 n = len(a)
 cost = [[0 for i in range(n)] for j in range(n)]
 for length in range(2, n+1):
  for i in range(0, n-length+1):
   k = i+length-1
   def f(i,j,k):
    return cost[i][j-1]+cost[j][k]+M[i][0]*M[j-1][1]*M[k][1]
   cost[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
 return cost[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print solve(M)

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

n = input()
M = []

for i in range(n):
  M.append(map(int, raw_input().split()))
print mcm(M)

Solution (Python):
def edit_distance(M):
  n = len(M)



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

    for i in range(0, n-long+1):

      j = i + long - 1

      def a(i, k ,j):
        return m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1]
      m[i][j] = min(a(i, k, j) for k in range(i, j))
   
  return m[0][n-1]
 
n = input()
M = []
 
for i in range(n):
  M.append(map(int, raw_input().split()))
print edit_distance(M)

Solution (Python):
N = input()
M = [map(int, raw_input().split()) for i in xrange(N)]
cache = {}
for i in xrange(N):
    cache[(i, i+1)] = 0
def dfs(left, right):
    if (left, right) in cache:
        return cache[(left, right)]
    min_cost = float("inf")
    for mid in xrange(left+1, right):
        tmp = M[left][0] * M[mid-1][1] * M[right-1][1]
        tmp += dfs(left, mid)
        tmp += dfs(mid, right)
        if min_cost > tmp:
            min_cost = tmp
    cache[(left, right)] = min_cost
    return min_cost
print dfs(0, len(M))

Solution (Python):
def cost(i,k,j):
 return m[i][k] + m[k+1][j] + p[i][0] * p[k][1] * p[j][1]

n = input()
p = []
m = [[0 for i in xrange(n)] for j in xrange(n)]
for i in xrange(n):
 p.append(map(int, raw_input().split()))

N = len(p)
for l in xrange(2,N+1):
 for i in xrange(0,N-l+1):
   j = i+l-1
   m[i][j] = min(cost(i,k,j) for k in xrange(i,j))

print m[0][N-1]

Solution (Python):
n = int(input())
p = []
a,b = [int(x) for x in input().split()]
p.append(a)
p.append(b)
for i in range(1, n):
    c,d = [int(x) for x in input().split()]
    p.append(d)


dp = []
for x in range(n+1):
    dp.append([0] * (n+1))

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

        for k in range(i, j):
            tmp = dp[i][k] + dp[k+1][j] + (p[i-1] * p[k] * p[j])
            if dp[i][j] > tmp:
                dp[i][j] = tmp

print(dp[1][n])

Solution (Python):
def cost( i,k,j ):
  return m[i][k] + m[k+1][j] + M[i][0] * M[k][1] * M[j][1]
 
n = input()
M = []
m = [[ 0 for i in range(n) ] for j in range(n) ]
for i in range(n):
  M.append( map (int, raw_input().split() ) )
 
M_long = len(M)
for l in range( 2,M_long+1 ):
  for i in range( 0,M_long-l+1 ):
    j = i+l-1
    m[i][j] = min( cost( i,k,j ) for k in range( i,j ) )
 
print m[0][M_long-1]

Solution (Python):
n = input()
M = []
 
def scalar(n):
   m = [[0 for i in range(len(n))] for j in range(len(n))]
 
   for l in range(2, len(n)+1):
      for i in range(0, len(n)-l+1):
         j = i + l - 1
         m[i][j] = min(m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1] for k in range(i, j))
 
   print m[0][len(n)-1]
 
for i in range(n):
   M.append(map(int, raw_input().split()))
scalar(M)

Solution (Python):
MAX = pow(10, 8)
N = 100
p = [None] * (N + 1)
m = [None] * (N + 1)
n = input()
for i in xrange(1, n + 1):
    m[i] = [None] * (N + 1)
    m[i][i] = 0
    p[i - 1], p[i] = map(int, raw_input().split())
    
for l in xrange(2, n + 1):
    for i in xrange(1, n - l + 2):
        j = i + l - 1
        m[i][j] = MAX
        for k in xrange(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 = input()
M = [map(int, raw_input().split()) for i in xrange(N)]
cache = {}
for i in xrange(N):
    cache[(i, i+1)] = 0
def dfs(left, right):
    if (left, right) in cache:
        return cache[(left, right)]
    min_cost = float("inf")
    for mid in xrange(left+1, right):
        tmp = M[left][0] * M[mid-1][1] * M[right-1][1]
        tmp += dfs(left, mid)
        tmp += dfs(mid, right)
        if min_cost > tmp:
            min_cost = tmp
    cache[(left, right)] = min_cost
    return min_cost
print dfs(0, len(M))

Solution (Python):
n = int(raw_input())
p = [0 for i in range(0, 101)]
m = [[0 for i in range(0, 101)] for j in range(0, 101)]
for i in range(1, n+1):
    p[i-1], p[i] = map(int, raw_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):
            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 = input()
X = []
  
def matrix(n):
   x = [[0 for i in range(len(n))] for j in range(len(n))]
  
   for l in range(2, len(n)+1):
      for i in range(0, len(n)-l+1):
         j = i + l - 1
         x[i][j] = min(x[i][k] + x[k+1][j] + X[i][0]*X[k][1]*X[j][1] for k in range(i, j))
  
   print x[0][len(n)-1]
  
for i in range(n):
   X.append(map(int, raw_input().split()))

matrix(X)

Solution (Python):
n = input()
p = [0 for row in range(101)]
m = [[0 for col in range(n+1)] for row in range(n+1)]
for i in range(1, n+1):
  p[i-1], p[i] = map(int, raw_input().split())

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

print m[1][n]

Solution (Python):
n = input()
M = []
  
def scalar(n):
   m = [[0 for i in range(len(n))] for j in range(len(n))]
  
   for l in range(1, len(n)):
      for i in range(0, len(n)-l):
         j = i + l
         m[i][j] = min(m[i][k] + m[k+1][j] + M[i][0]*M[k+1][0]*M[j][1] for k in range(i, j))
  
   return m[0][len(n)-1]
  
for i in range(n):
   M.append(map(int, raw_input().split()))
print scalar(M)

Solution (Python):
n = input()

p = [0 for i in xrange(n + 1)]

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

for i in xrange(1, n + 1):
    m[i][i] = 0
    
for l in xrange(2, n + 1):
    for i in xrange(1, n - l + 2):
        j = i + l - 1
        m[i][j] = float("inf")
        for k in xrange(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(raw_input())
p = [0 for i in range(0, 101)]
m = [[0 for i in range(0, 101)] for j in range(0, 101)]

for i in range(1, n+1):
   p[i-1], p[i] = map(int, raw_input().split())
     
for k in range(2, n+1):
   for i in range(1, n-k+2):
      j = i+k-1
      m[i][j] = float("inf")
      for l in range(i, j):
         m[i][j] = min(m[i][j], m[i][l] + m[l+1][j] + p[i-1]*p[l]*p[j])
 
print m[1][n]

Solution (Python):
n = int(input())
p = [0 for i in range(n+1)]
m = [[0 for i in range(100)] for j in range(100)]

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):
            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 mcm(M):
  n = len(M)
  m = [[0 for i in range(n)] for j in range(n)]
   
  for l in range(2, n+1):
    for i in range(0, n-l+1):
      j = i + l - 1
      def cost(i, k ,j):
        return m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1]
      m[i][j] = min(cost(i, k, j) for k in range(i, j))
   
  return m[0][n-1]
 
n = input()
M = []
 
for i in range(n):
  M.append(map(int, raw_input().split()))
print mcm(M)

Solution (Python):
n = int(raw_input())
p = [0 for i in range(0, 101)]
m = [[0 for i in range(0, 101)] for j in range(0, 101)]
for i in range(1, n + 1):
    p[i-1], p[i] = map(int, raw_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):
            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(n):
    x = [[0 for i in range(len(n))] for j in range(len(n))]
    for l in range(2, len(n)+1):
        for i in range(0, len(n)-l+1):
            j = i + l - 1
            x[i][j] = min(x[i][k] + x[k+1][j] + X[i][0]*X[k][1]*X[j][1] for k in range(i, j))

    print x[0][len(n)-1]

n = input()
X = []

for i in range(n):
    X.append(map(int, raw_input().split()))

matrix(X)

Solution (Python):

N = 100
n = input()
p = [0 for i in xrange(N+1)]
m = [[0 for i in xrange(N+1)] for j in xrange(N+1)]
for i in xrange (1,n+1):
    p[i-1],p[i] = map(int,raw_input().split())
    m[i][i] = 0
for l in xrange (2,n+1):
    for i in xrange(1,n-l+2):
        j = i + l - 1
        m[i][j] = 10**10
        for k in xrange(i,j):
            m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j])
print max(max(m))

Solution (Python):
def matrix(X):
    x = [[0 for i in range(len(X))] for j in range(len(X))]
    for l in range(2, len(X)+1):
        for i in range(0, len(X)-l+1):
            j = i + l - 1
            x[i][j] = min(x[i][k] + x[k+1][j] + X[i][0]*X[k][1]*X[j][1] for k in range(i, j))

    print x[0][len(X)-1]

n = input()
X = []

for i in range(n):
    X.append(map(int, raw_input().split()))

matrix(X)

Solution (Python):
n = int(raw_input())
p = [0 for i in range(0, 101)]
m = [[0 for i in range(0, 101)] for j in range(0, 101)]
for i in range(1, n+1):
    p[i-1], p[i] = map(int, raw_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):
            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(X):
    m = [[0 for i in range(len(X))] for j in range(len(X))]

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

    print m[0][len(X)-1]

n = input()
X = []

for i in range(n):
    X.append(map(int, raw_input().split()))

matrix(X)

Solution (Python):
def matrix(X):
    m = [[0 for i in range(len(X))] for j in range(len(X))]

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

    print m[0][len(X) - 1]

n = input()
X = []

for i in range(n):
    X.append(map(int, raw_input().split()))

matrix(X)

Solution (Python):
n = int(raw_input())
p = [0 for i in range(0, 101)]
m = [[0 for i in range(0, 101)] for j in range(0, 101)]

for i in range(1, n+1):
    p[i-1], p[i] = map(int, raw_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):
            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 chain(p,n):
    m={}
    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] = float("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])

p={}
n = int(input())
for i in range(1,n+1):
    st = input()
    w = st.split()
    p[i-1] = int(w[0])
    p[i]   = int(w[1])
chain(p,n)

Solution (Python):
n = int(input())
m = []


def memoize(f):
    memo = [[None] * n for _ in range(n)]
    for i in range(n):
        memo[i][i] = 0

    def main(b, e):
        if memo[b][e] is not None:
            return memo[b][e]
        result = memo[b][e] = f(b, e)
        return result

    return main


@memoize
def contract(b, e):
    return min(contract(b, i) + contract(i + 1, e) + m[b] * m[i + 1] * m[e + 1] for i in range(b, e))


r, c = map(int, input().split())
m.append(r)
m.append(c)
nc = n - 1
while nc:
    r, c = map(int, input().split())
    m.append(c)
    nc -= 1

print(contract(0, n - 1))

Solution (Python):
def main():
    n = int(raw_input())
    m = [ [0] * n for _ in xrange(n)]
    p = [ 0 for _ in xrange(n+1)]
    for i in xrange(n):
        a = map(int, raw_input().split())
        if i == 0:
            p[0] = a[0]
            p[1] = a[1]
        else:
            p[i+1] = a[1]

    for l in xrange(2,n+1):
        for i in xrange(0,n-l+1):
            j = i + l -1
            m[i][j] = float('inf')
            for k in xrange(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[0][n-1]
    return 0

main()

Solution (Python):
n = int(input())
p = [0] * (n + 1)
m = [[0 for _ in range(100)] for _ in range(100)]

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):
            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(raw_input())
p = [0 for i in range(n+2)]
for i in range(1, n+1):
    a, b = map(int, raw_input().split())
    p[i] = a
p[n+1] = b

M = [[0 for i in range(n+1)] for j in range(n+1)]
for d in range(1, n+1):
    for i in range(1, n-d+1):
        j = i+d
        msf = M[i][i] + M[i+1][j] + p[i]*p[i+1]*p[j+1]
        for k in range(i, j):
            msf = min(msf, M[i][k] + M[k+1][j] + p[i]*p[k+1]*p[j+1])
        M[i][j] = msf
print M[1][n]

Solution (Python):
import sys

def multiply(M, N, memo):
    for i in range(1, N):
        for s in range(N - i):
            l, r = s, s + i
            mincost = 1000000
            for j in range(l, r):
                mincost = min(mincost, memo[l][j] + memo[j + 1][r] + M[l][0] * M[j + 1][0] * M[r][1])
            memo[l][r] = mincost

lines = sys.stdin.readlines()
N = int(lines[0])
del lines[0]
memo = [[0 for i in range(N)] for j in range(N)]
M = []
for line in lines:
    M.append(map(int, line.split()))
multiply(M, N, memo)
print memo[0][N - 1]

Solution (Python):
import sys

def multiply(M, N, memo):
    for i in range(1, N):
        for l in range(N - i):
            r = l + i
            memo[l][r] = min(memo[l][j] + memo[j + 1][r] + M[l][0] * M[j + 1][0] * M[r][1] for j in range(l, r))

lines = sys.stdin.readlines()
del lines[0]
M = []
for line in lines:
    M.append(map(int, line.split()))
N = len(M)
memo = [[0 for i in range(N)] for j in range(N)]
multiply(M, N, memo)
print memo[0][N - 1]

Solution (Python):
def matrixChainMultiplication(n):
    m = [[0 for x in range(n + 1)] for y 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] = 99000001
            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])


p = []

n = int(input())

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

p.append(int(listed_input[1]))

matrixChainMultiplication(n)

Solution (Python):
import sys

def mcm(sizes, memo, l, r):
    if l == r:

        return 0
    if memo[l][r] >= 0:

        return memo[l][r]

    m = sys.maxsize
    for k in range(l, r):
        m = min (m, mcm(sizes, memo, l, k) + mcm(sizes, memo, k+1, r) + sizes[l][0] * sizes[k][1] * sizes[r][1])
    memo[l][r] = m
    return memo[l][r]

if __name__ == '__main__':
    
    n = int(input())
    x = []
    for _ in range(n):
        y = tuple(map(int, input().split(' ')))
        x.append(y)
    
    
    memo = []
    for _ in range(n):
        memo.append([-1]*n)

    print( mcm(sizes = x, memo=memo, l = 0, r = n-1) )

Solution (Python):
def get_multi_num(M):
    D = {}
    def get_multi_num_core(M):
        if len(M) < 2: return 0
        key = tuple(M)
        if key in D: return D[key]
        result = [None]*(len(M)-1)
        for i in range(1,len(M)):
            result[i-1] = get_multi_num_core(M[:i]) + \
                          get_multi_num_core(M[i:]) + \
                          M[0][0]*M[i][0]*M[-1][1]
        D[key] = min(result)
        return D[key]
    return get_multi_num_core(M)
        
if __name__=='__main__':
    n = int(input())
    M = [None]*n
    for i in range(n):
        M[i] = tuple(map(int,input().split()))
    print(get_multi_num(M))

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

dp = [[10**7]*(n+1) for i in range(n+1)]  

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+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] + c[i-1]*c[k]*c[j])

print(dp[1][n])

Solution (Python):
import sys

def dp(n, size):
  list = [[sys.maxint for i in range(n)] for j in range(n)]
  for i in range(n):
    list[i][i] = 0
  for l in range(2, n+1):
    for i in range(0, n-l+1):
      for it in range(1, l):
        list[i][i+l-1] = min(list[i][i+l-1], list[i][i+it-1] + list[i+it][i+l-1] + size[i]*size[i+it]*size[i+l])
  print list[0][n-1]

n = int(raw_input())
size = [0 for i in range(n+1)]
for i in range(n):
  line = raw_input().split()
  size[i] = int(line[0])
  size[i+1] = int(line[1])
dp(n, size)

Solution (Python):
import functools


@functools.lru_cache(maxsize=None)
def rec(l, r):
    
    if l+1 == r:
        return 0
    ret = INF
    for mid in range(l+1, r):
        ret = min(ret, rec(l, mid) + rec(mid, r) + R[l] * R[mid] * C[r-1])
    return ret

INF = 10**9
N = int(input())
R, C = [], []
for i in range(N):
    r, c = map(int, input().split())
    R.append(r), C.append(c)
print(rec(0, N))

Solution (Python):
def calc(p):
    n = len(p) - 1
    m = [[None for i in range(n + 1)] for j in range(n + 1)]
    for x in range(n):
        m[x][x] = 0
    for l in range(2, n + 1):
        for i in range(0, n - l + 1):
            j = i + l - 1
            m[i][j] = float("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())
p = []
for i in range(n):
    inp = list(map(int, input().split()))
    if i == 0:
        p.append(inp[0])
        p.append(inp[1])
    elif 0 < i < n - 1:
        p.append(inp[1])
    elif i == (n - 1):
        p.append(inp[1])

m = calc(p)
print(m[0][n - 1])

Solution (Python):
import sys

n = int(input())

c = [0]*(n+1)
c[0],c[1] = map(int,input().split())

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

dp = [[sys.maxsize]*(n+1) for i in range(n+1)]

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+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]+c[i-1]*c[k]*c[j])


print(dp[1][n])

Solution (Python):

def chain(p,n):
    m={}
    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] = float("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])
    
if __name__=="__main__": 
    p={}
    n = int(input())
    for i in range(1,n+1):
        st = input()
        w = st.split()
        p[i-1] = int(w[0])
        p[i]   = int(w[1])
    chain(p,n)

Solution (Python):



import sys


def mat_mul_opt(_mat_info):
    r, c = map(int, _mat_info[0])
    rc_info.extend([r, c])
    for each in _mat_info[1:]:
        rc_info.append(int(each[1]))

    for l in range(2, mat_num + 1):
        for i in range(1, mat_num - l + 2):
            j = i + l - 1
            ans[i][j] = 1e7
            for k in range(i, j):
                ans[i][j] = min(ans[i][j], ans[i][k] + ans[k + 1][j] +
                                rc_info[i - 1] * rc_info[k] * rc_info[j])

    return ans[1][mat_num]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    mat_num = int(_input[0])
    mat_info = tuple(map(lambda x: x.split(), _input[1:]))

    rc_info = []
    ans = [[0] * (mat_num + 1) for _ in range(mat_num + 1)]
    print(mat_mul_opt(mat_info))

Solution (Python):



import sys


def mat_mul_opt(_mat_info):
    rc_info.extend(list(map(int, _mat_info[0])))
    rc_info.extend(list(map(lambda x: int(x[1]), _mat_info[1:])))

    for l in range(2, mat_num + 1):
        for i in range(1, mat_num - l + 2):
            j = i + l - 1
            ans[i][j] = 1e7
            for k in range(i, j):
                ans[i][j] = min(ans[i][j], ans[i][k] + ans[k + 1][j] +
                                rc_info[i - 1] * rc_info[k] * rc_info[j])

    return ans[1][mat_num]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    mat_num = int(_input[0])
    mat_info = tuple(map(lambda x: x.split(), _input[1:]))

    rc_info = []
    ans = [[0] * (mat_num + 1) for _ in range(mat_num + 1)]
    print(mat_mul_opt(mat_info))

Solution (Python):



import sys


def mat_mul_opt(_mat_info):
    rc_info = list(map(int, _mat_info[0]))
    rc_info.extend(list(map(lambda x: int(x[1]), _mat_info[1:])))

    for l in range(2, mat_num + 1):
        for i in range(1, mat_num - l + 2):
            j = i + l - 1
            ans[i][j] = 1e7
            for k in range(i, j):
                ans[i][j] = min(ans[i][j], ans[i][k] + ans[k + 1][j] +
                                rc_info[i - 1] * rc_info[k] * rc_info[j])

    return ans[1][mat_num]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    mat_num = int(_input[0])
    mat_info = tuple(map(lambda x: x.split(), _input[1:]))
    

    ans = [[0] * (mat_num + 1) for _ in range(mat_num + 1)]
    print(mat_mul_opt(mat_info))