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:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

DEBUG = True
DEBUG = False

def dbg(*args):
    if DEBUG:
        print("DBG: ", file=sys.stderr, end="")
        print(*args, file=sys.stderr)

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

Submission status: Accepted

Solution code:
def matrixChainMultiplication():
    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] = 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[1][n]

if __name__ == "__main__":
    INF = 10000000000000
    p = []
    n = int(input())
    m = [[None] * (n+1) for i in range(n+1)]
    for i in range(n):
        inp = list(map(int, input().split()))
        if i == 0:
            p.append(inp[0])
            p.append(inp[1])
        else:
            p.append(inp[1])
    print(matrixChainMultiplication())

Submission status: Accepted

Solution code:
from pprint import pprint

n = int(input().strip())
for i in range(n):
    line = input().strip().split()
    if i == 0:
        mat = [int(line[0]), int(line[1])]
    else:
        mat.append(int(line[1]))
#pprint(mat)
dp = [[-999999999] * (n+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][i] = 0

for i in range(n, 0, -1):
    for j in range(i+1, n+1):
        #for k in range(i, j):
        #    print(i, k, j)
        #    print((i, k), (k+1, j), dp[i][k], dp[k+1][j])
        #    print(dp[i][k], dp[k-1][j], mat[i-1] * mat[k] * mat[j])
        #    assert(dp[i][k] >= 0)
        #    assert(dp[i+j-k][j] >= 0)
        dp[i][j] = min(dp[i][k] + dp[k+1][j] + mat[i-1] * mat[k] * mat[j] for k in range(i, j))
        #print("--")

#pprint(dp)
print(dp[1][n])

Submission status: Accepted

Solution code:
# coding=utf-8


def calc_cost():
    global M
    for diff in range(0, n):
        for i in range(1, n-diff+1):
            j = i + diff
            if diff == 0:
                M[i][j] = 0
            elif diff == 1:
                M[i][j] = p[i-1] * p[i] * p[j]
            else:
                M[i][j] = calc_min(i, j)
            ### debugger ###
            #for row in M:
            #    print(*row)
    return M[1][n]

def calc_min(i, j):
    global M, p
    min_cost = float("inf")
    for k in range(i, j):
        cost = M[i][k] + M[k+1][j] + (p[i-1] * p[k] * p[j])
        #print("i, j, k, cost:", i, j, k, cost)
        if cost < min_cost:
            min_cost = cost
    return min_cost

n = int(input())
M = [["-" for _ in range(n+1)] for _ in range(n+1)]
r_list = []
c_list = []
p = []
for _ in range(n):
    r, c = map(int, input().split())
    r_list.append(r)
    c_list.append(c)

p.append(r_list[0])
for c in c_list:
    p.append(c)

total_cost = calc_cost()
print(total_cost)

Submission status: Accepted

Solution code:
def main():
    n = input()
    p = map(int,raw_input().split())
    for i in xrange(1,n):
        p.append(map(int,raw_input().split())[1])

    print mcm(p)

def mcm(p):
    n = len(p)-1
    m = [[0]*(n+1) for i in xrange(n+1)]

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

    return m[1][n]
            

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(raw_input())
matrix = []
for i in range(n):
    a = map(int, raw_input().split())
    matrix.append([a[0], a[1]])

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

for l in range(2, n+1):
    for i in range(1, n-l+2):
        j = i + l - 1
        m[i][j] = 10**19
        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:
INF = 1e9

def MatrixChainMulti(n, p):
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
    
    for i in range(n+1):
        dp[i][i] = 0
        
    for l in range(1, n): # 1<= l <= n-1
        for i in range(0, n-l+1): #0<= i <= n-l
            j = i + l
            dp[i][j] = INF
            for k in range(i, j): # i<= k <= j-1
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j])
    
    return dp[1][n]

N = int(input())
p = []
a, b = list(map(int, input().split()))
p.append(a)
p.append(b)

for _ in range(N-1):
    c, d = list(map(int, input().split()))
    p.append(d)
    
print(MatrixChainMulti(N, p))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
p = [0 for _ in range(N+1)]

p[0], p[1] = map(int, input().split())
for n in range(2, N+1):
    p[n] = list(map(int, input().split()))[1]

M = [[0]*(N+1) for _ in range(N+1)]

for n in range(N+1):
    M[n][n] = 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])

Submission status: Accepted

Solution code:
def matrix_chain_multiplication(n, list):
    matrix = [[0 for i in range(n)] for j in range(n)]

    for i in range(n-1):
        for j in range(n-i-1):
            k = j+i+1
            matrix[j][k] = float('inf')
            for r in range(j, k):
                matrix[j][k] = min(matrix[j][k],
                    matrix[j][r] + matrix[r+1][k]
                    + list[j]*list[r+1]*list[k+1])

    return matrix[0][n-1]

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

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

    print(matrix_chain_multiplication(n, list))

Submission status: Accepted

Solution code:
def main():
    """ MAIN """
    DAT = []
    num = int(input())
    for i in range(num):
        x, y = list(map(int,input().split()))
        DAT.append(x)
    DAT.append(y)
    num1 = num + 1
    TBL = [[0] * num1 for i in range(num1)]

    for i in range(0, num1):
        for row in range(num-i):
            col = row + i + 1
            for j in range(row+1,col):
                x = DAT[row] * DAT[j] * DAT[col] + TBL[row][j] + TBL[j][col]
                if TBL[row][col] < 1 or TBL[row][col] > x:
                    TBL[row][col] = x

    print("{}".format(TBL[row][col]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N = input()


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

    p = [0] * N

    for i in range (N):
        p[i],dummy  = map(int, raw_input().split())
        
    p.append(dummy)

    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 = int(input())
p = list(range(n+2))

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

# table[i][j] : M_i??????M_j??????????????????????°?????????°
table = [[0] * (n+1) for i in range(n+1)]

# ??£????????£???2????????????????????????
for i in range(1,n):  # 1<=i,i+1<=n
    table[i][i+1] = p[i]*p[i+1]*p[i+2]


for k in range(3, n+1):    # ?????????k???????????????????????????3<=k<=n
    for i in range(1,n+2-k): # M_i?????????1<=i<=n-k+1
        j = i + k - 1      # M_j?????§???k??????

        table[i][j] = float('inf')

        for x in range(i, j): # M_i~M_x??¨M_(x+1)~M_j??§????????????(i<=x,x+1<=j<=n)
            # print(i, x, j)
            cost = table[i][x] + table[x+1][j] + p[i]*p[x+1]*p[j+1]
            table[i][j] = min(table[i][j], cost)
            

print(table[1][n])

Submission status: Accepted

Solution code:
n = int(input())
INF = 10**9
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] = INF
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + P[i][0] * P[k][1] * P[j][1])

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

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):
            m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i][0] * p[k][1] * p[j][1])

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

Submission status: Accepted

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

n = int(input())
p = []
m = dict()
for _ in range(n):
    r, c = map(int, input().split())
    p.append(r)
    if _ == n-1:
        p.append(c)

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

print(m[(1, n)])

Submission status: Accepted

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


if __name__ == '__main__':

    n = int(input())
    p = [0]
    for _ in range(n):
        r, c = list(map(int, input().split(" ")))
        p[-1] = r
        p.append(c)
    m = [[0 for i in range(n+1)] for j 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
            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:
import sys
INF = float("inf")
n = int(input())
A = [0]
for i, a in enumerate(sys.stdin):
    a = list(map(int, a.split()))
    if i == 0:
        A.extend(a)
    else:
        A.append(a[1])
C = [[INF] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
    C[i][i] = 0
for j in range(1, n):
    for i in range(1, n - j + 1):
        for k in range(i + 1, i + j + 1):
            cost = C[i][k - 1] + C[k][i + j] + A[i] * A[k] * A[i + j + 1]
            if cost < C[i][i + j]:
                C[i][i + j] = cost
print(C[1][n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
INF = float("inf")
n = int(input())
z = []
m = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    a, b = map(int, input().split())
    z.append(a)
z.append(b)
for l in range(1, n):
    for i in range(1, n - l + 1):
        j = i + l
        m[i][j] = 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:
import sys
INF = float("inf")
n = int(input())
m = [[0] * (n + 1) for _ in range(n + 1)]
li = [list(map(int, a.split())) for a in sys.stdin]
z = (li[0][0], ) + list(zip(*li))[1]
for l in range(1, n):
    for i in range(1, n - l + 1):
        j = i + l
        m[i][j] = 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:
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 l in range(2,n):
 for i in range(1,n-l+1):
  j=i+l-1;m[i][j]=1e6
  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-1])

Submission status: Accepted

Solution code:
import sys
n=int(input())+1
e=list(map(lambda x:x.split(),sys.stdin))
p=[int(e[0][0])]+list(int(x[1])for x in e)
m=[[0]*n for _ in[0]*n]
for l in range(2,n):
 for i in range(1,n-l+1):
  j=i+l-1;m[i][j]=1e6
  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-1])

Submission status: Accepted

Solution code:
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 l in range(2,n):
  for i in range(1,n-l+1):
   j=i+l-1;m[i][j]=1e6
   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-1])
if'__main__'==__name__:s()

Submission status: Accepted

Solution code:
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 1>m[r][c]or m[r][c]>x:m[r][c]=x
 print(m[r][c])
if'__main__'==__name__:s()

Submission status: Accepted

Solution code:
import sys
def s():
 n=int(input())+1
 e=list(map(lambda x:x.split(),sys.stdin))
 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 1>m[r][c]or m[r][c]>x:m[r][c]=x
 print(m[r][c])
if'__main__'==__name__:s()

Submission status: Accepted

Solution code:
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 1>m[r][c]or m[r][c]>x:m[r][c]=x
 print(m[r][c])
s()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

memo = []
for _ in range(n):
    memo.append([-1]*n)


def mul(i, j):
    if i == j:
        return 0
    if memo[i][j] >= 0:
        return memo[i][j]
    num = 100000
    for k in range(i, j):
        num = min(num, mul(i, k) + mul(k+1, j) + data[i][0] * data[k][1] * data[j][1])
    memo[i][j] = num
    return memo[i][j]

print(mul(0, n-1))

Submission status: Accepted

Solution code:

from functools import lru_cache


@lru_cache(maxsize=None)
def multi(ms):
    """Matix multiplication. returns minimum number of scalar
    multiplications to compute all matrix multiplications.

    >>> multi(((30, 35), (35, 15), (15, 5), (5, 10), (10, 20), (20, 25)))
    15125
    """
    size = len(ms)
    if size <= 1:
        return 0
    elif size == 2:
        r1, c1 = ms[0]
        r2, c2 = ms[1]
        return c1 * r1 * c2

    costs = []
    for i in range(size-1):
        cost = ms[i][1] * ms[0][0] * ms[-1][1]
        costs.append(multi(ms[:i+1]) + multi(ms[i+1:]) + cost)

    return min(costs)


def run():
    n = int(input())
    ms = []

    for i in range(n):
        m = tuple([int(x) for x in input().split()])
        ms.append(m)

    print(multi(tuple(ms)))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
INFTY = float('inf')

n = int(input())
M = [[0 for i in range(n)] for i in range(n)]
p = []

for i in range(n):
    r, c = list(map(int, input().split(' ')))
    if i == 0: p.append(r)
    p.append(c)

for i in range(n-1):
    M[i][i+1] = p[i]*p[i+1]*p[i+2]

for gap in range(2,n): # gap = 1,.., n-1
    for i in range(n-gap):
        j = i+gap
        M[i][j] = INFTY
        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 = []
for i in range(N):
    r, c = map(int, input().split())
    if i == 0:
        P.append(r)
    P.append(c)


def matrix_chain():
    dp = [[None for j in range(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
            dp[i][j] = 1000000000000000
            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])

    return dp[1][N]


def main():
    print(matrix_chain())


if __name__ == '__main__':
    main()

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:
# -*- coding: utf-8 -*-
import functools
INF = 10**9
n = int(input())
p = list(map(int, input().split()))
for i in range(n - 1):
    p.append(int(input().split()[1]))


@functools.lru_cache(maxsize=None)
def matrix_chain_multiplication(i, j):
    if i == j:
        return 0

    tmp = INF
    for k in range(i, j):
        tmp = min(
            tmp,
            matrix_chain_multiplication(i, k) +
            matrix_chain_multiplication(k + 1, j) + p[i - 1] * p[k] * p[j])
    return tmp


print(matrix_chain_multiplication(0, n - 1))

Submission status: Accepted

Solution code:
import sys
n = int(input())
input_list = [[int(i) for i in str.split()] for str in sys.stdin.read().splitlines()]
size_list = [0 for i in range(n+1)]
size_list[0] = input_list[0][0]
for i in range(1,n+1):
    size_list[i] = input_list[i-1][1]


m = [[float('inf') for i in range(n)] for j in range(n)]

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

for x in range(n):
    i, j = 0, x
    for y in range(n-x):
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + size_list[i]*size_list[k+1]*size_list[j+1])
        i, j = i+1, j+1

print(m[0][-1])

Submission status: Accepted

Solution code:
n = int(input())
p = []
s = input().split()
p.append(int(s[0]))
p.append(int(s[1]))
for _ in range(n - 1):
    s = input().split()
    p.append(int(s[1]))

m = [[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):
    m[i][i] = 0

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

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

Submission status: Accepted

Solution code:
#coding:utf-8
n = int(input())
m = [[0 for i in range(n)] for j in range(n)]
p = []
for i in range(n):
    p1,p2 = map(int,input().split())
    if i == 0:
        p.append(p1)
    p.append(p2)

def matrixChainMultiplication():
    for i in range(n):
        m[i][i] = 0

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

Submission status: Accepted

Solution code:
#coding: utf-8
import sys

ROW = 0
COL = 1

def matrixchaincost(M):
    n = len(M)
    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][ROW]*M[j-1][COL]*M[k][COL]
            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 matrixchaincost(M)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main():
    num_mat = int(stdin.readline())
    r = [int(s) for s in stdin.readline().split()]
    for _ in range(num_mat-1):
        _, row = (int(s) for s in stdin.readline().split())
        r.append(row)

    if num_mat < 2:
        print(0)
        return
    elif num_mat < 3:
        print(r[0]*r[1]*r[2])
        return

    M = []
    M.append([0] * num_mat)
    M.append([r[i]*r[i+1]*r[i+2] for i in range(len(M[-1])-1)])

    for i in range(2, num_mat):
        N = []
        for j in range(num_mat-i):
            N.append(min(M[k][j]+M[i-1-k][1+j+k]+r[j]*r[1+j+k]*r[i+1+j]
                         for k in range(i)))
        M.append(N)
    print(M[-1][0])


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
p0, p1 = map(int, input().split())
p = [p0, p1]
for _ in range(1, n):
    _, tmp = map(int, input().split())
    p.append(tmp)
# M[i]: p[i-1] * p[i]size

dp = [[0]*(n+1) for _ in range(n+1)]
#dp[i][j]: M[i]...M[j] の掛け算最小回数

for i in range(0, n+1):
    dp[i][i] = 0
# for i in range(1, n+1):
#     for j in range(i+1, n+1):
#         for k in range(i, j):
#             # M[i]...M[k], M[k+1]...M[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])

for w in range(2, n+1):
    for i in range(1, n+1):
        j = i+w-1
        if j >= n+1:
            continue
        res = 1e30
        for k in range(i, j):
            res = min(
                res,
                dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]
            )
        dp[i][j] = res
print(dp[1][n])

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
def end_of_loop():raise StopIteration
    
    
def main():
    N = I()
    A = [0]*N
    B = [0]*N
    if N == 0:
        sys.exit()
    for i in range(N):
        a, b = MI()
        A[i] = a
        B[i] = b

    D = Init(N, N, 0)
    #tableの初期化
    for num1 in range(N-1):
        num2 = num1+1
        a,b,c = A[num1], B[num1], B[num2]
        D[num1][num2] = a*b*c
        D[num2][num1] = a*b*c

    for length in range(2, N):
        for num1 in range(N-length):
            num2 = num1+length
            #num1からnum2-1までの組み合わせで最小値を求める
            a = A[num1]
            c = B[num2]
            result = float('inf')
            for num3 in range(num1, num2):
                result = min(result, a*B[num3]*c + D[num1][num3] + D[num3+1][num2])
            D[num1][num2] = result
            D[num2][num1] = result
    print(D[0][N-1])
            
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# [New] Matrix Chain Multiplication using Dynamic Programming Formula
# https://www.youtube.com/watch?v=_WncuhSJZyA

n = int(input())

P = []
a, b = [int(i) for i in input().split()]
P.append(a)
P.append(b)
for _ in range(n - 1):
    _, b = [int(i) for i in input().split()]
    P.append(b)

dp = [[None] * (n + 1) for _ in range(n + 1)]  # 1-indexed table

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

for r in range(2, n + 1):
    for i in range(1, n - r + 2):
        j = i + r - 1
        dp[i][j] = float("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][-1])

Submission status: Accepted

Solution code:
n = int(input())


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

    def inner_memo(a, b):
        if memo[a][b] is not None:
            return memo[a][b]
        rslt = memo[a][b] = f(a, b)
        return rslt

    return inner_memo

@memorizer
def minimum(a, b):
    return min(minimum(a, i) + minimum(i + 1, b) + l[a] * l[i + 1] * l[b + 1] for i in range(a, b))



a, b = map(int, input().split())

l = []
l.append(a)
l.append(b)

n1 = n - 1

while n1 != 0:
    a, b = map(int, input().split())
    l.append(b)
    n1 -= 1

print(minimum(0, n - 1))

Submission status: Accepted

Solution code:
N = int(input())
RC = [tuple(map(int, input().split())) for _ in range(N)]
INF = 10**18
# dp[i][j]: iからjの区間における最小回数
dp = [[INF]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            dp[i][j] = 0
for diff in range(2, N+1):
    for i in range(N-diff+1):
        j = i+diff-1
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+RC[i][0]*RC[k][1]*RC[j][1])
print(dp[0][N-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def matrixChainMultiplication(n):
    for l in range(2, n+1):
        for i in range(1, n-l+2):
            j = i + l - 1
            min_ = 2**21 # 十分大きい数
            for k in range(i, j):
                value = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
                if min_ > value:
                    min_ = value
            m[i][j] = min_

m = [[0]*(101) for _ in range(101)]
p = [0] * 101
N = int(input())
l0 = list(map(int, input().split()))
p[0] = l0[0]
p[1] = l0[1]
for _ in range(1, N):
    li = list(map(int, input().split()))
    p[_+1] = li[1]
matrixChainMultiplication(N)
print(m[1][N])

Submission status: Accepted

Solution code:
#区間[l,r]での最小値は?
#区間[l,l+mid]の最小値+[l+mid+1,r]の最小値+midに依存した計算回数
#(Mi Mj)*(Mj Mk)の計算回数はijk

def kuDP(l,r):
  global dp
  
  if dp[l][r] != -1:
    return dp[l][r]
  
  if l == r:
    dp[l][r] = 0
    return 0
  
  if l+1 == r:
    c = M[l][0]*M[l][1]*M[r][1]
    dp[l][r] = c
    return c
  
  midl = [10**10]*(r-l)
  for mid in range(r-l):
    midl[mid] = kuDP(l,l+mid) + kuDP(l+mid+1,r) + M[l][0]*M[l+mid][1]*M[r][1]
    
  c = min(midl)
  
  dp[l][r] = c
  
  return c

N = int(input())
M = [list(map(int,input().split())) for _ in range(N)]
dp = [[-1]*N for _ in range(N)]
print(kuDP(0,N-1))

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    p = [0] * (N + 1)
    for i in range(N):
        p[i], p[i + 1] = il()

    for l in range(2, N + 1):
        for i in range(1, N - l + 2):
            j = i + l - 1
            dp[i][j] = MAX
            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()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def matrixChainMultiplication(n,p):
    dp = [[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
            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])
    return dp[1][n]


def main():
    N = int(readline())
    P = []

    for _ in range(N):
        r, c = map(int, readline().split())
        P.append(r)
    P.append(c)

    print(matrixChainMultiplication(N,P))

    


if __name__ == '__main__':
    main()