Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

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



Sample input:
6
30 35
35 15
15 5
5 10
10 20
20 25


Sample output:
15125

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:

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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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]

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys

def mcm(sizes, memo, l, r):
    if l == r:
#        print('a:', l, r)
        return 0
    if memo[l][r] >= 0:
#        print('b:', l, r)
        return memo[l][r]
#    print('c:', 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__':
    # Load input
    n = int(input())
    x = []
    for _ in range(n):
        y = tuple(map(int, input().split(' ')))
        x.append(y)
    
    # Create memo:
    memo = []
    for _ in range(n):
        memo.append([-1]*n)
#    print(x)
    print( mcm(sizes = x, memo=memo, l = 0, r = n-1) )

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)]  # dp[i][j] <- M_i~M_j

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

for l in range(2, n+1):  # l=j-i+1(length of chain)
    for i in range(1, n-l+2):
        j = i+l-1
        for k in range(i, j):  # kirutokoro
            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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import functools


@functools.lru_cache(maxsize=None)
def rec(l, r):
    # [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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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) :#length of chain j-i+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])

Submission status: Accepted

Solution code:
#coding:UTF-8
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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:]))
    # assert len(mat_info) == mat_num

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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:])))

    ans = [[0] * (mat_num + 1) for _ in range(mat_num + 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:]))
    # assert len(mat_info) == mat_num

    print(mat_mul_opt(mat_info))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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:])))

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

    for l in range(1, mat_num):
        for i in range(1, mat_num - l + 1):
            j = i + l
            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:]))
    # assert len(mat_info) == mat_num

    print(mat_mul_opt(mat_info))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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:])))

    ans = [[0] * (mat_num + 1) for _ in range(mat_num + 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] = float('inf')
            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:]))
    # assert len(mat_info) == mat_num

    print(mat_mul_opt(mat_info))

Submission status: Accepted

Solution code:
def matrixChainMultiplication(p):
    # p = [p_0, p_1, ..., p_n]
    n = len(p) - 1
    # n+1 x n+1 zero matrix?????????(0,...,n)
    # cost(i,j): (M_i...M_j)???????°??????????
    cost = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for numOfMatrices in range(2, n + 1):
        for i in range(1, n - numOfMatrices + 2):
            j = i + numOfMatrices - 1
            cost[i][j] = float('inf')
            for k in range(i, j):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k + 1][j] + p[i - 1] * p[k] * p[j])
    print(cost[1][n])

p = []
n = int(input())

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

matrixChainMultiplication(p)

Submission status: Accepted

Solution code:
n = int(input())

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


for l in range(1,n):
    for i in range(0,n-l):
        j = i + l
        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]*p[k+1]*p[j+1])   
   
print(m[0][n-1])

Submission status: Accepted

Solution code:
n = int(input())

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

for l in range(1,n):
    for i in range(0,n-l):
        j = i + l
        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]*p[k+1]*p[j+1])


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import random
import sys
import os
import pprint


"""Matrix Chain Multiplication"""

#fd = os.open('ALDS1_10_B.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

n = int(input())
col = [0] * (n + 1)
for i in range(n):
    row, column = map(int, input().split())
    col[i] = row
    col[i+1] = column

memo = [[0 for i in range(n+1)] for j in range(n+1)]
#pprint.pprint(memo)

for length in range(2, n+1):
    for start_index in range(1, n - length + 2):
        end_index = start_index + length - 1
        candidates = []
        for split_index in range(start_index, end_index):
            left = memo[start_index][split_index]
            right = memo[split_index + 1][end_index]
            plus = col[start_index - 1] * col[split_index] * col[end_index]
            candidates.append(left + plus + right)

        memo[start_index][end_index] = min(candidates)
        #print('memo', start_index, end_index, memo[start_index][end_index])

#pprint.pprint(memo)
print(memo[1][n])

Submission status: Accepted

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

m = [[0] * n for i in range(n)]

for l in range(2, n + 1):
  for i in range(n - l + 1):
    j = i + l - 1
    m[i][j] = float('inf')
    for k in range(i, j):
      cost = m[i][k] + m[k + 1][j] + p[i][0] * p[k][1] * p[j][1]
      m[i][j] = min(m[i][j], cost)

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

Submission status: Accepted

Solution code:
def maxChain(n,p):
    m = [[0 for i in range(n+1)] for i 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] = 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 str(m[1][n])
n = int(input())
p = []
for i in range(n):
    L = list(map(int, input().split()))
    if i == 0:
        p.append(L[0])
        p.append(L[1])
    else:
        p.append(L[1])
print(maxChain(n,p))

Submission status: Accepted

Solution code:
def matrixChainMultiplication(M):
    # P ??????
    n = len(M)
    P = [M[0][0]]
    P += [M[i][1] for i in range(n)]
    # ?¨???¶?????? m ??????
    m = [[[] for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
            m[i][i] = 0

    # l???????±???¨?????????????????°
    for l in range(2, n + 1):
        for i in range(1, n - l + 2):
            j = i + l - 1
            m[i][j] = 9999999999999999
            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]


if __name__ == '__main__':
    n = int(input())
    M = [list(map(int, input().split())) for _ in range(n)]
    print(matrixChainMultiplication(M))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)

inf = float('inf')

def solve():
    n = int(sys.stdin.readline())

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

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

    memo = [[-1]*(n + 1) for i in range(n + 1)]

    ans = mcm(memo, n, r, c, 0, n)

    # print(memo)

    print(ans)

def mcm(memo, n, r, c, left, right):
    if memo[left][right] != -1:
        return memo[left][right]
    elif right - left == 1:
        memo[left][right] = 0
        return 0
    else:
        res = inf

        for i in range(left + 1, right):
            res = min(res, mcm(memo, n, r, c, left, i) + mcm(memo, n, r, c, i, right) + r[left]*r[i]*c[right-1])

        memo[left][right] = res
        return res

def compute_lcs(x, y):
    n = len(x)
    m = len(y)

    x = '#' + x
    y = '#' + y

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

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if x[i] == y[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[n][m]

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)

inf = float('inf')

def solve():
    n = int(sys.stdin.readline())

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

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

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

    for ls in range(2, n + 1):
        for i in range(n - ls + 1):
            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)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
m = [[0 for j in range(n + 1)] for i in range(n + 1)]
z = [0] * (n + 1)
for i in range(1, n + 1):
    z[i - 1], z[i] = map(int, input().split())
j = 0
for l in range(2, n + 1):
    for i in range(1, n - l + 2):
        j = i + l - 1
        m[i][j] = int(1e8)
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + z[i - 1] * z[k] * z[j])
print(m[1][n])

Submission status: Accepted

Solution code:
n = int(input())
m = [[0] * (n + 1) for _ in range(n + 1)]
z = [0] * (n + 1)
for i in range(n):
    z[i], z[i + 1] = map(int, input().split())
j = 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] + z[i - 1] * z[k] * z[j])
print(m[1][n])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import re
import math
import collections
import itertools
import functools
import logging

logging.basicConfig(level=logging.DEBUG, format="DBG: %(message)s")

def dbg(msg, *args, **kwargs):
    logging.debug(msg, *args, **kwargs)

Mat = collections.namedtuple("Mat", "r c")

def mat_mul(ms):
    return Mat(ms[0].r, ms[-1].c)

def cost(m1, m2):
    return m1.r * m1.c * m2.c

def solve(n, ms):
    if n == 1: return 0

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

    for l in range(2, n+1):
        for i in range(n-l+1):
            #cost_min = math.inf
            cost_min = float("inf")
            for j in range(l-1):
                #dbg("l, i, j: %d %d %d", l, i, j)
                m_lhs = mat_mul(ms[i:i+j+1])
                m_rhs = mat_mul(ms[i+j+1:i+l])
                #dbg("m_lhs, m_rhs: %r %r", m_lhs, m_rhs)
                cost_lhs = dp[(i,i+j)]
                cost_rhs = dp[(i+j+1,i+l-1)]
                #dbg("cost_lhs, cost_rhs: %d %d", cost_lhs, cost_rhs)
                cost_mul = cost(m_lhs, m_rhs)
                #dbg("cost_mul: %d", cost_mul)
                cost_now = cost_mul + cost_lhs + cost_rhs
                #dbg("cost_now: %d", cost_now)
                if cost_min > cost_now:
                    cost_min = cost_now
            dp[(i,i+l-1)] = cost_min

    #dbg(dp)
    return dp[(0,n-1)]

def main():
    n = int(input())

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

    print(solve(n, ms))

if __name__ == "__main__": main()