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




from collections import deque
import sys
input = sys.stdin.readline

def main():
    nmax = 1000000
    n = int(input())
    p = []
    calc = [[nmax for i in range(n + 1)] for i in range(n + 1)]

    for i in range(n):
        (a,b) = map(int,input().split())
        p.append(a)
    else:
        p.append(b)

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

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

            for j in range(s):
                m = calc[i][i+j] + calc[i+j+1][i+s] + p[i-1]*p[i+j]* p[i+s]

                if calc[i][i+s] > m:
                    calc[i][i+s] = m
    print (calc[1][n])
if __name__ == '__main__':
    main()

Solution (Python):
def matrix_chain_multiplication(n, m, p):
    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 m


n = int(input())
N = 100
p = [0 for i in range(N+1)]
m = [[0 for a in range(N+1)] for b in range(N+1)]

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

Solution (Python):
INF = 10**20
n = int(input())
nlist = []
all_mat = []
for i in range(n):
    a,b = map(int, input().split())
    all_mat.append((a,b))
    if (i == 0):
        nlist = [a,b]
    else:
        nlist.append(b)
        
def cost1(nlist):
    if len(nlist) == 0:
        return 0
    m = min(nlist)
    cost = 0
    mid = nlist.index(m)
    a = nlist[:mid]
    b = nlist[mid+1:]
    while (len(a)>1 and len(a) !=0):
        for i in range(len(a)-1):
            cost += a.pop()*a[-1]
            
    while (len(b)>1 and len(b) !=0):
        b.reverse()
        for i in range(len(b)-1):
            cost += b.pop()*b[-1]
            
    if (len(a) == 1 and len(b) == 1):
        cost += a.pop()*b.pop()
        
    cost *= m
    return cost

def cost2(nlist, mm):
    if len(nlist) == 0:
        return 0
    m = min(nlist)
    cost = 0
    mid = nlist.index(m)
    a = nlist[:mid+1]
    
    b = nlist[mid:]
    
    while (len(a)>1 and len(a) !=0):
        a.reverse()
        for i in range(len(a)-1):
            cost += a.pop()*a[-1]
            
    while (len(b)>1 and len(b) !=0):
        for i in range(len(b)-1):
            cost += b.pop()*b[-1]
            
    if (len(a) == 1 and len(b) == 1):
        cost += m*mm
        
    cost *= mm
    return cost

copy = nlist[:]
m = min(nlist)

c = nlist.count(m)
cost = 0
if (c == 1):
    cost = cost1(nlist)
elif (c >= 2):
    cc = 1
    cut_index = [0]
    mcount = nlist.count(m)
    for i in range(mcount):
        cut_index.append(nlist.index(m))
        nlist.remove(m)
    cut = []
    for i in range(mcount):
        cut.append(nlist[cut_index[i]:cut_index[i+1]])
    cut.append(nlist[cut_index[-1]:])
    
    co1 = cut[0] +[m]+ cut[-1]
    cost += cost1(co1)
    for co2 in cut[1:-1]:
        
        cost += cost2(co2,m)
    co3 = cut[0]+cut[-1]
    if (len(co3)>1):
        cost += (len(cut)-2)*m*min(co3)
print(cost)

Solution (Python):
def least_multiplication(mtx):
    N = len(mtx)
    mul = [[None] * N for x in range(N)]

    for i in range(N):
        mul[i][i] = 0
    

    for chain in range(1, N):
        for begin in range(N-chain):
            end = begin + chain
            cand = []
            for j in range(begin, end):
                left = mul[begin][j]
                down = mul[j+1][end]
                this = mtx[begin][0] * mtx[j][1] * mtx[end][1]
                cand.append(left + down + this)
            mul[begin][begin+chain] = min(cand)
        
    return mul[0][N-1]


def main():
    n = int(input())
    matrices = []
    for i in range(n):
        col, row = map(int, input().split())
        matrices .append((col, row))
    ans = least_multiplication(matrices)
    print(ans)


main()

Solution (Python):
global memo

def find_memo(m,l):
                            
    if(memo[m][l]!=0):
        return memo[m][l]
    
    if(m<2):
        return memo[m][l]
    

    tmp_min=999999999
    for i in range(1,m):
        left=find_memo(i,l)
        right=find_memo(m-i,l+i)
        middle=memo[0][l]*memo[0][l+i]*memo[0][l+m]
        if(left + right + middle< tmp_min):
            tmp_min = left + right + middle
    memo[m][l]=tmp_min
    return tmp_min




tmp_min=9999999999
n=int(input())
memo=[[0]*(n+1-i) for i in range(n+1)]

memo[0][0],memo[0][1]=map(int,input().split())
for i in range(2,n+1):
    dummy,memo[0][i]= map(int,input().split())

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

print(find_memo(n,0))

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





T = [[0]*n for _ in range(n)]


for p in range(1, n):
    for i in range(n-p):
        j = i + p
        val = float("inf")
        for k in range(i,j):
            val_tmp = T[i][k] + T[k+1][j] + r[i]*c[k]*c[j]
            if val_tmp < val:
                val = val_tmp
        T[i][j] = val
        
print(T[0][n-1])

Solution (Python):
N = int(input())
R = [0]*N
C = [0]*N
for i in range(N):
    R[i], C[i] = map(int, input().split())

INF = 10**18
dp = [[INF]*N for i in range(N)]
for i in range(N):
    dp[i][i] = 0
for l in range(1, N):
    for i in range(N-l):
        a0 = R[i]
        c0 = C[i+l]
        dp[i][i+l] = min(a0*C[j]*c0 + dp[i][j] + dp[j+1][i+l] for j in range(i, i+l))
print(dp[0][N-1])

Solution (Python):

import sys

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

dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for l in range(2, N + 1):
    for i in range(1, N - l + 2):
        j = i + l - 1
        dp[i][j] = sys.maxsize
        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):
def multi_chain_multiplication(n, P):
    M = [[0]*(n+1) for _ in range(n+1)]

    if 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 M[i][j]
    else:
        return 0

def read_and_print_min_multiplication(n):
    P = [0] * (n+1)
    for i in range(n):
        A = [int(i) for i in input().split()]
        if i == 0:
            P[i] = A[0]
            P[i+1] = A[1]
        else:
            P[i+1] = A[1]
    print(multi_chain_multiplication(n, P))

n = int(input())
read_and_print_min_multiplication(n)

Solution (Python):



from sys import maxsize


def irange(start, stop=None):
    if stop:
        return range(start, stop + 1)
    else:
        return range(start + 1)


def count(ms):
    n = len(ms)

    p = [0] * (n + 1)
    for i in range(n):
        p[i] = ms[i][0]
        p[i + 1] = ms[i][1]

    m = [[None] * (n + 1) for _ in irange(n)]
    for i in irange(1, n):
        m[i][i] = 0
    for l in irange(2, n):
        for i in irange(1, n - l + 1):
            j = i + l - 1
            m[i][j] = maxsize
            for k in irange(i, j - 1):
                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]


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

    m = []
    for _ in range(n):
        m.append(tuple(int(x) for x in input().split()))
    c = count(m)
    print(c)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
p0, p1 = list(map(int, input().split()))
p = [p0, p1]
for i in range(n-1):
    pi = list(map(int, input().split()))
    p.append(pi[1])
    
dp = [[10**10]*(n+2) for _ in range(n+2)]

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

Solution (Python):
import sys
def calc(i,j):
    if i == j:
        return 0
    elif j-i == 1:
        return A[i][0]*A[i][1]*A[j][1]
    else:
        if d[i][j]:
            return d[i][j]
        else:
            ret = sys.maxsize
            for k in range(i,j):
                tmp = calc(i,k)+calc(k+1,j)+A[i][0]*A[k][1]*A[j][1]
                if tmp < ret:
                    ret = tmp
            d[i][j] = ret
            return ret

n = int(input())
A = []
d = [[None for _ in range(n)] for _ in range(n)]
for i in range(n):
    a,b = [int(i) for i in input().split()]
    A.append((a,b))
print(calc(0,n-1))

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

N_MAX = 100
M_MAX = 1 << 21
m = [[-1] * (n+1) for i in range(n+1)]

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

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

print(m[1][n])

Solution (Python):
n = int(input())
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])
 
array = [[10**7]*(n+1) for i in range(n+1)]
 
for i in range(1, n+1):
    array[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):
            array[i][j] = min(array[i][j], array[i][k] + array[k+1][j] + c[i-1]*c[k]*c[j])
 
print(array[1][n])

Solution (Python):
import sys
 
n = int(input())
 
mlist = [0]*(n+1)

mlist[0],mlist[1] = map(int,input().split())

for i in range(2,n+1):
    mlist[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]+mlist[i-1]*mlist[k]*mlist[j])
 
print(dp[1][n])

Solution (Python):

INFTY = float('inf')
MAX = 200
size = int(input())

C = [[INFTY for _ in range(MAX+1)] for i in range(MAX+1)]
R = [0 for i in range(MAX+2)]
for i in range(size):
    a,b = map(int, input().split())
    if i == 0:
        R[1] = a
    R[i+2] = b

for i in range(1, size+1): C[i][i] = 0

for j in range(1,size):
    for i in range(1,size):
        for k in range(i+1,i+j+1):
            cost = C[i][k-1] + C[k][i+j] + R[i]*R[k]*R[i+j+1]
            if cost < C[i][i+j]:
                C[i][i+j] = cost
print(C[1][size])