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(input())
p = []
a, b = map(int, input().split())
p.append(a)
p.append(b)
for _ in range(n-1):
    a, b = map(int, input().split())
    p.append(b)

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

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    lst=tuple(tuple(map(int,input().split())) for _ in range(n))

    dp=[[0]*n for _ in range(n)]
    for i in range(1,n):
        for j in range(0,n-i):
            dp[j][j+i]=dp[j+1][j+i]+lst[j][0]*lst[j][1]*lst[j+i][1]
            for k in range(1,i):
                nwork=dp[j][j+k]+dp[j+k+1][j+i]+lst[j][0]*lst[j+k][1]*lst[j+i][1]
                if dp[j][j+i]>nwork : dp[j][j+i]=nwork
    
    print(dp[0][n-1])

main()

Submission status: Accepted

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

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

INF = 1 << 60
dp = [[INF] * n for _ in range(n)]

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

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

print(dp[0][-1])

Submission status: Accepted

Solution code:
N = int(input())
RC = []
for _ in range(N):
    RC.append(list(map(int, input().split())))

dp = {}

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

for w in range(2, N+1):
    for l in range(N-w+1):
        cost = float('inf')
        r = l+w-1
        for m in range(l, r):
            mul = RC[l][0] * RC[m][1] * RC[r][1]
            cost = min(cost, dp[(l, m)]+dp[(m+1,r)] + mul)
        dp[(l, r)] = cost
print(dp[(0, N-1)])

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]

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

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

Submission status: Accepted

Solution code:
INF = 10**10


def rec(l:int, r:int) -> int:
    if dp[l][r] != INF:
        return dp[l][r]
    elif r - l == 1:
        dp[l][r] = 0
        return 0
    elif r - l == 2:
        dp[l][r] = M[l][0] * M[l][1] * M[l+1][1]
        return dp[l][r]
    else:
        for i in range(l+1, r):
            dp[l][r] = min(dp[l][r], rec(l, i) + rec(i, r) + M[l][0] * M[i-1][1] * M[r-1][1])
    return dp[l][r]


if __name__ == "__main__":
    N = int(input())
    M = [tuple(map(int, input().split())) for _ in range(N)]
    dp = [[INF]*(N+1) for _ in range(N+1)]
    print(rec(0, N))

Submission status: Accepted

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

DP = [[0]*N for _ in range(N)]
for l in range(2, N+1): # l は行列の数
    for i in range(0, N):
        j = i + l-1
        if j >= N:
            break
        
        DP_ji = 10**9
        for k in range(i, j):
            DP_ji = min(DP_ji
                        ,DP[k][i] + DP[j][k+1] + r[i]*c[k]*c[j])
        DP[j][i] = DP_ji
print(DP[N-1][0])

Submission status: Accepted

Solution code:
N = int(input())

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

dp = [[float("inf")]*N for _ in range(N)]

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

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

print(dp[0][-1])

Submission status: Accepted

Solution code:
n = int(input())
INFTY = 10**8

p = [0]*(n+1)
for i in range(n):
    roww = input().split()
    p[i] = int(roww[0])
    p[i+1] = int(roww[1])

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

def matricChainMultiplication(n, p, M):
#     2つの行列積のmin, 次は3という風に増やしていく
    for l in range(2, n+1):
        for i in range(0, n - l + 1):
            j = i + l - 1 #積を見る最大のIndex
            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(l, i, j, k, M[i][j])
    return M[0][n-1]

print(matricChainMultiplication(n, p, M))

Submission status: Accepted

Solution code:
import sys

N = 100
n = int(input())

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

for i in range(n):
    p[i],p[i+1]=map(int,input().split())
for l in range(2,n+1):
    for i in range(1,n-l+2):
        j = i+l-1
        m[i][j]=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])

print(m[1][n])

Submission status: Accepted

Solution code:
n = int(input())
r = [0] * (n+1) # M1=r0*r1, M2=r1*r2, ... , Mn=rn-1*rn
m = [[100**4] * (n+1) for _ in range(n+1)] # m[i][j] = Mi...Mj の最小コスト
for i in range(n):
    r[i], r[i+1] = list(map(int, input().split()))

for i in range(1, n+1): # 1個の行列のコスト
    m[i][i] = 0
for i in range(1, n): # 2個の行列のコスト
    m[i][i+1] = r[i-1] * r[i] * r[i+1]
for j in range(2, n): # j+1 個の行列のコスト
    for i in range(1, n-j+1): # Mi...Mi+j
        for k in range(j): # Mi...Mi+k と Mi+k+1...Mi+j に分割
            # print('i=',i,' i+k=',i+k,' i+j=', i+j)
            cost = m[i][i+k] + r[i-1]*r[i+k]*r[i+j] + m[i+k+1][i+j]
            if cost < m[i][i+j]:
                m[i][i+j] = cost
print(m[1][n])

Submission status: Accepted

Solution code:
N = int(input())
m = []
for i in range(N):
  x,y = map(int,input().split())
  m.append((x,y))

dp = [ [0]*N for _ in range(N) ]
for i in range(N):
  dp[i][i] = 0

for L in range(1,N): 
  for i in range(N-L): 
    j = i+L
    dp[i][j] = float('inf')
    for k in range(i,j):
      m0,m1,m2 = m[i],m[k],m[j]
      # print(i,j,k,m0,m1,m2)
      dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+m0[0]*m1[1]*m2[1])

print(dp[0][-1])

Submission status: Accepted

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

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):
        j = i + l
        dp[i][j] = INF
        for k in range(i,j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + P[i-1] * P[k] * P[j])

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

Submission status: Accepted

Solution code:
n=int(input())
m={}
p=[]

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

for l in range(2,n+1):
    for i in range(1,n-l+2):
        j=i+l-1
        m[i][j]=10000000
        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 = [0]*(n+1)
m = [[None for _ in range(n+1)] for _ in range(n+1)]
for i in range(1,n+1):
    p[i-1],p[i] = map(int,input().split())
    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

input = sys.stdin.readline
INF = float("inf")


def main():
    n = int(input())
    r = [None] * n
    c = [None] * n
    for i in range(n):
        r[i], c[i] = map(int, input().split())

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

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    p = []
    for i in range(N):
        a, b = map(int, input().split())
        p.append(a)
    else:
        p.append(b)

    m = [[1e10]*(N+1) for _ in range(N+1)]
    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] = 1e10
            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__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10 ** 9 + 7

# map(int, input().split())
# list(map(int, input().split()))

N = int(input())
M = [0] * N
for i in range(N):
    M[i] = tuple(map(int, input().split()))

dp = [[INF] * (N) for _ in range(N)]
for i in range(N):
    dp[i][i] = 0

def rec(l, r):
    if dp[l][r] != INF:
        return dp[l][r]
    res = INF
    for mid in range(l, r):
        res = min(res, rec(l, mid) + rec(mid + 1, r) + M[l][0] * M[mid][1] * M[r][1])
    dp[l][r] = res
    return res
print(rec(0, N - 1))

Submission status: Accepted

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

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

for i in range(2, n+1): #幅
    for j in range(0, n+1-i): #左端
        dp[j][j+i] = min([dp[j][k]+(r[j]*c[k-1]*c[j+i-1])+dp[k][j+i] for k in range(j+1,j+i)])

print(dp[0][n])

Submission status: Accepted

Solution code:
# Solution to this problem using memoization
# https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_10_B

import math

# Optimal cost of multiplying A_1 A_2 ... A_j
def cost(i, j):
    if (i, j) in cost_dict.keys():
        return cost_dict[(i, j)]
    elif i == j:
        cost_dict[(i, j)] = 0
    else:
        mincost = math.inf
        for k in range(i, j):
            estimate = cost(i, k) + cost(k + 1, j) + dims[i - 1] * dims[k] * dims[j]
            mincost = min(estimate, mincost)
        cost_dict[(i, j)] = mincost
    return cost_dict[(i, j)]


if __name__ == '__main__':
    # Number of matrices
    n = int(input())
    # A dictionary to store costs
    cost_dict = dict()
    # Take input dimensions
    dims = []
    for _ in range(n - 1):
        first = int(input().split()[0])
        dims.append(first)
    dims.extend(list(map(int, input().split())))
    # Calculate the optimal cost
    print(cost(1, n))

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/10/ALDS1_10_B
# 普通に難しい
# アイデアは写真の解説を参照

# データの入力
N = int(input())

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

# dpテーブルの用意 minを取るときはinf埋めしておくと処理が楽になるしバグが見つかりやすい
INF = 2**32-1
dp = [[INF]*N for _ in range(N)]

# dpテーブルの初期化
# 対角成分0
for ij in range(N):
    dp[ij][ij] = 0

# dpの更新 どう更新しているのか、なんでこう更新するのかは写真を参照
for l in range(1, N):  # lは対角成分からいくつ離れているか (なん個行列をかけるかという解釈も可)
    for i in range(N):
        j = i+l
        if j >= N:
            continue
        for k in range(i, j):  # 最小値探索
            dp[i][j] = min(dp[i][k] + dp[k+1][j] +
                           P[i] * P[k+1] * P[j+1], dp[i][j])
print(dp[0][-1])

Submission status: Accepted

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

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

def mincost(x,y):
    if dp[x][y]>0:
        return dp[x][y]
    elif x>=y:
        return dp[x][y]
    else:
        res=float('inf')
        for k in range(x,y):
            temp=mincost(x,k)+mincost(k+1,y)+M[x][0]*M[k][1]*M[y][1]
            res=min(res,temp)
        dp[x][y]=res
        return dp[x][y]

print(mincost(0,n-1))

Submission status: Accepted

Solution code:

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

dp=[[10**10]*(n) for i in range(n)]    
#dp=[[0]*(n+1) for i in range(n+1)]    
    
#dp[0][1]=p[0]*p[1]*p[2]
dp[0][0]=0
for j in range(1,n):
    for i in range(j,-1,-1):
#        print("-------------i:",i,"j:",j)
        if j==i:
            dp[i][j]=0
#            print("i:",i,"j:",j,"k:",999)
        else:
#            for k in range(i+1,j):
            for k in range(j-1,i-1,-1):
#                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j])
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+p[i]*p[k+1]*p[j+1])
#                print("i:",i,"j:",j,"k:",k)
#                print(dp[i][j],dp[i][k],dp[k+1][j],p[i-1]*p[k]+p[j])
print(dp[0][n-1])

Submission status: Accepted

Solution code:
n = int(input())
mat = []
for _ in range(n):
    mat.append(list(map(int, input().split())))
inf = int(1e11 + 10)
dp = [[inf]*(n + 1) for _ in range(n + 1)]
for i in range(n):
    dp[i][i] = 0
for l in range(2, n + 1):
    for i in range(n):
        j = i + l - 1
        if i + l > n:
            break
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + mat[i][0]*mat[k][1]*mat[j][1])
print(dp[0][n - 1])

Submission status: Accepted

Solution code:
def solve(n,mat):
    dp=[[0]*n for _ in range(n)]
    for kukan in range(1,n):
        for i in range(n-kukan):
            dp[i][i+kukan]=min([dp[i][mid]+dp[mid+1][i+kukan]+mat[i][0]*mat[mid+1][0]*mat[i+kukan][1] for mid in range(i,i+kukan)])
    return dp[0][n-1]

n=int(input())
mat=[tuple(map(int,input().split())) for _ in range(n)]
print(solve(n,mat))

Submission status: Accepted

Solution code:
def solve(a, b):
    global dp
    if a == b:
        return 0
    elif dp[a][b]:
        return dp[a][b]
    ret = INF
    for i in range(a, b):
        tmp = solve(a, i) + solve(i + 1, b) + c[i] * r[a] * c[b]
        ret = min(ret, tmp)
    dp[a][b] = ret
    return ret

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

INF = float('inf')
dp = [[0 for _ in range(n)] for _ in range(n)]
print(solve(0, n - 1))

Submission status: Accepted

Solution code:
# ALDS_10_B - 連鎖行列積

import sys

N = int(input())

M = []
for n in range(N):
    r, c = map(int, sys.stdin.readline().strip().split())
    if n == 0:
        M.append(r)
    M.append(c)


# dp 初期化
dp = [[float('inf')] * N for _ in range(N)]
for n in range(N):
    dp[n][n] = 0

# dp 更新
for l in range(1, N):
    for i in range(N - l):
        j = i + l
        for k in range(i, j):
            # print(f'k: {k}, i: {i}, j: {j}')
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + M[i] * M[k + 1] * M[j + 1])

# for i in range(len(dp)):
#     print(dp[i])

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

Submission status: Accepted

Solution code:
n = int(input())
p = [None] * (n+1)# i番目の列数 = i+1番目の行数
for i in range(n):
  p[i], p[i+1] = map(int, input().split())

INF = 10**18
m = [[None] * 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(n-l+1):
    j = i + l - 1# [i, j]の範囲の計算の最小コストを考える
    m[i][j] = INF
    for k in range(i,j):
      m[i][j] = min(m[i][j], m[i][k]+m[k+1][j] + p[i-1]*p[k]*p[j])

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

Submission status: Accepted

Solution code:
N = int(input())
M = [[int(x) for x in input().split()] for _ in range(N)]

p = []

for m in M:
    p.append(m[0])

p.append(M[-1][1])

dp = [[0] * N for j in range(N)]

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

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

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_B&lang=ja

import sys
sys.setrecursionlimit(10**7)



def rec(l,r):
    if r-l < 1:
        return 0
    if r-l == 1:
        return M[l][0] * M[r][0] * M[r][1]
    if memo[l][r] != -1:
        return memo[l][r]
    memo[l][r] = min(rec(l, j-1) + rec(j, r) + M[l][0] * M[j-1][1] * M[r][1] for j in range(l+1,r+1))
    return memo[l][r]



N = int(input())
M = []
memo = [[-1]*N for _ in range(N)]

for i in range(N):
    M.append(list(map(int, input().split())))

print(rec(0,N-1))

Submission status: Accepted

Solution code:
n =int(input())
R = [0]*(n+1)
C = [0]*(n+1)
for u in range(n):
    R[u+1], C[u+1] = map(int, input().split())

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

print(dp[1][n])

Submission status: Accepted

Solution code:
MAX_R = 100
MAX_C = 100
n = int(input())
mat_list = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1] * (MAX_C + 1) for _ in range(MAX_R + 1)]

def get_min(i, j):
    ans = float('inf')
    if dp[i][j] != -1:
        return dp[i][j]
    if i == j:
        ans = 0
    else:
        for k in range(i, j):
            p = mat_list[i][0]
            q = mat_list[k][1]
            r = mat_list[j][1]
            tmp = get_min(i, k) + get_min(k+1, j) + p*q*r
            if tmp < ans:
                ans = tmp
    dp[i][j] = ans
    return ans

print(get_min(0, n-1))

Submission status: Accepted

Solution code:
N = int(input())
RC = [0] * N
for i in range(N):
  RC[i] = list(map(int, input().split()))
  
dp = [[float("inf")] * (N + 1) for _ in range(N + 1)]
for l in range(N + 1):
  for r in range(l, N + 1):
    if abs(l - r) <= 1:
      dp[l][r] = 0
    elif abs(l - r) == 2:
      dp[l][r] = RC[l][0] * RC[l][1] * RC[l + 1][1]
      
#print(dp)
#print("")
now = 3
while now <= N:
  for l in range(N + 1):
    #print(l, now)
    r = l + now
    if r <= N:
      for k in range(l + 1, r):
        dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + RC[l][0] * RC[k][0] *RC[r - 1][1])
  now += 1
        
print(dp[0][N])

Submission status: Accepted

Solution code:
import sys

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
m = [[INF]*N for i in range(N)]
for i in range(N):
    m[i][i] = 0
for l in range(1, N):
    for i in range(N-l):
        a0 = R[i]
        c0 = C[i+l]
        m[i][i+l] = min(a0*C[j]*c0 + m[i][j] + m[j+1][i+l] for j in range(i, i+l))
print(m[0][N-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
p=[]
for i in range(n):
    s,c = map(int,input().split())
    if i == 0:
        p.append(s)
    p.append(c)


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

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

print(m[1][n])

Submission status: Accepted

Solution code:
import sys
INFTY=sys.maxsize

def main(n,m,p):
    #global m
    #global p

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

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


n=int(input())
p=[]
k,l=list(map(int,input().split()))
i=1
p.append(k)
p.append(l)
while(i<n):
    l,m=list(map(int,input().split()))
    p.append(m)
    i+=1

m=[]
for i in range(n+1):
    mm=[0]*(n+1)
    m.append(mm)

main(n,m,p)

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_B&lang=ja
# http://algorithms.blog55.fc2.com/blog-entry-66.html
# https://www.geeksforgeeks.org/python-program-for-matrix-chain-multiplication-dp-8/
import sys

sys.setrecursionlimit(10 ** 6)
n = int(input())
r = []
for i in range(n):
    a, b = map(int, input().split())
    if i == 0:
        r.append(a)
        r.append(b)
    else:
        r.append(b)

dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]


# dp[i][j] MiMi+1...Mjを計算する最適なコスト
# M[1][2] = M[1][1] + M[2][2] +
def chain_order(i, j):
    if i == j:
        return 0
    if dp[i][j] != float('inf'):
        return dp[i][j]
    for k in range(i, j):
        dp[i][j] = min(dp[i][j], chain_order(i, k) + chain_order(k + 1, j) + r[i - 1] * r[k] * r[j])
    return dp[i][j]


# print(r)
print(chain_order(1, len(r)-1))

Submission status: Accepted

Solution code:
INF = float('inf')
mm = [(-1,-1)]
n = int(input())
for _ in range(n):
    mm.append(tuple((map(int,input().split()))))

def scala(a,b,c):
    return mm[a][0] * mm[b][1] * mm[c][1] 

dp = [[INF for _ in range(n+1)] for _ in range(n+1)]
#init
for i in range(1,n):
    dp[i][i+1] = mm[i][0] * mm[i+1][1] * mm[i][1]
    dp[i][i] = 0
dp[-1][-1] = 0
#begin dp
for d in range(2,n):
    for l in range(1,n-d+1):
        r = l + d
        for m in range(l,r):
            dp[l][r] = min(dp[l][m] + dp[m+1][r] + scala(l,r,m), dp[l][r])
print(dp[1][n])
#for i in range(n+1):
#    print(dp[i])
#for d in range(2,n):
#    for l in range(1,n-d+1):
#        r = l + d
#        for m in range(l,r):
#            dp[l][r] = max(dp[l][m] + dp[m+1][r] + scala(l,r,m), dp[l][r])

#print(dp[1][n])
#for i in range(n+1):
#    print(dp[i])

Submission status: Accepted

Solution code:
from functools import lru_cache, reduce
from sys import stdin
from operator import mul

@lru_cache(maxsize=None)
def getMin(args:tuple):
    if len(args) == 2:
        return 0
    elif len(args) == 3:
        return reduce(mul, args)
    l = [(args[0:i+1], args[i:], args[0]*args[i]*args[-1]) for i in range(1, len(args)-1)]
    return min([getMin(v[0]) + getMin(v[1]) + v[2] for v in l])


n = int(input())
M = [tuple(map(int, line.split())) for line in stdin.readlines()]
R = tuple([M[0][0]] + [r[1] for r in M])
print(getMin(R))

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
inf=float('inf')
def search(A,N):
    dp=[[inf for x in range(N+1)] for j in range(N+1)]

    p=[]
    for i in range(N+1):
        dp[i][i]=0
        if i>=1:
            if i==1:
                p.append(A[i][0])
                p.append(A[i][1])
            else:p.append(A[i][1])
    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])
    return dp[1][-1]

N=int(input())
num_list = [[0, 0]]
for i in range(N):
    num_list.append(list(map(int,stdin.readline().strip().split())))
print(search(num_list,N))

Submission status: Accepted

Solution code:
n = int(input())
p = [0]*(n+1)

INF = 1000000000

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

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

def DFS(i,j):
    if dp[i][j] != -1:
        return dp[i][j]
    else:
        if j-i == 2:
            dp[i][j] = p[i]*p[i+1]*p[i+2]
            return dp[i][j]
        elif j-i == 1:
            dp[i][j] = 0
            return 0
        else:
            calculation_amount = INF
            for k in range(i+1,j):
                tmp = DFS(i,k) + DFS(k,j) + p[i]*p[j]*p[k] 
                calculation_amount = min(calculation_amount,tmp)
            dp[i][j] = calculation_amount
            return calculation_amount

print(DFS(0,n))

Submission status: Accepted

Solution code:
n = int(input())

M = []
for i in range(n):
    r, c = map(int, input().split())
    if i == 0: M.append(r)
    M.append(c)

dp = [[float("inf")] * (n+1) for _ 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] + M[i-1]*M[k]*M[j])

print(dp[1][n])

Submission status: Accepted

Solution code:
N=int(input())

input_=[N]
for n in range(N):
    input_.append(input())
    
P=[]
for n in range(N):
    P.append(int(input_[n+1].split()[0]))
    
P.append(int(input_[n+1].split()[1]))

M=[[0]*(N) for x in range(N)]

for n in range(1,N):
    for i in range(N-n):
        M[i][i+n]=10**100
        for k in range(i,i+n):
            P_0=P[i]
            P_1=P[k+1]
            P_2=P[i+n+1]
            M_=M[i][k]+M[k+1][i+n]+P_0*P_1*P_2
            M[i][i+n]=min(M[i][i+n],M_)
            
print(M[0][-1])

Submission status: Accepted

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


def solve(N,R,C):
    dp = [[float('inf')]*N for _ in range(N)]

    for i in range(N):
        dp[i][i]=0
    for i in range(N-1,-1,-1):
        for j in range(i+1,N):
            for k in range(i,j):
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+R[i]*C[k]*C[j])
    ans = dp[0][N-1]
    return ans
print(solve(N,R,C))

Submission status: Accepted

Solution code:
import sys

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

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

for i in range(n):
    p[i], p[i+1] = map(int, sys.stdin.readline().strip().split())

# dpテーブルの対角成分を初期値とし、右斜に更新していく
# 利用する行列の数
for l in range(2, n+1):
    # 利用する範囲（l個の行列のうちi - jの範囲の行列を扱う）
    for i in range(1, n-l+2):
        j = i + l - 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][n])

Submission status: Accepted

Solution code:
n = int(input())
nums = []
for _ in range(n):
    nums.append(tuple(map(int,input().split())))
# print(nums)
dp = [[10**9]*n for _ in range(n)]
for i in range(n):
    dp[i][i] = 0
# for i in range(n):
#     print(*dp[i])
for l in range(2,n+1):
    for i in range(n-l+1):
        for k in range(l-1):
            # print(l,i,k,dp[i][i+k],dp[i+k+1][i+l-1])
            dp[i][i+l-1] = min(dp[i][i+l-1],dp[i][i+k] + dp[i+k+1][i+l-1] + nums[i][0]*nums[i+k][1]*nums[i+l-1][1])
print(dp[0][n-1])
# for i in range(n):
#     print(*dp[i])

Submission status: Accepted

Solution code:
N = int(input())

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

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

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

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

print(dp[0][-1])

Submission status: Accepted

Solution code:
n = int(input())
p = [0]*(n+1)
for i in range(1,n+1): p[i-1],p[i] = map(int,input().split())
m = [[0]*(n+1) for _ in range(n+1)]
# 対象とする行列の数l
for l in range(2,n+1):
    # for i in range(n+1): print(m[i])    
    # print("/////////////////////////////////")
    # 対象とする行列の範囲i,j
    # iは1からn-(l-1)まで
    for i in range(1,n-l+2):
        j = i+l-1
        m[i][j] = float("inf")
        # (M_iM_i+1...M_k)(M_k+1...M_j)の乗算回数が最小となるkを探す
        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())
size = [int(i) for i in input().split()]
for _ in range(n - 1):
    _, a = map(int, input().split())
    size.append(a)
dp = [[0] * (n) for _ in range(n)]
# init
for i in range(n):
    dp[i][i] = 0
# solve
for l in range(1, n):
    for i in range(n - l):
        j = i + l
        min = 10 ** 9
        for k in range(i, j):
            tmp = dp[i][k] + dp[k + 1][j] + size[i] * size[k + 1] * size[j + 1]
            if tmp < min:
                min = tmp
        dp[i][j] = min
print(dp[0][-1])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

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

    # dp[i][j]: [i, j)の最小乗算数
    dp = [[0]*(n+1) for _ in range(n)]

    # 幅
    for i in range(2, n+1):
        # 開始位置
        for j in range(n-i+1):
            tmp = []
            # 切れ目
            for k in range(j+1, j+i):
                tmp.append(M[j][0]*M[k][0]*M[j+i-1][1]+dp[j][k]+dp[k][j+i])
            dp[j][j+i] = min(tmp)

    print(dp[0][n])

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def matrix_chain_multiplication(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] = 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(n):
    listed_input = input().split()
    p.append(int(listed_input[0]))

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

matrix_chain_multiplication(n)

Submission status: Accepted

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

P=[M[0][0]]
for i in range(n):P.append(M[i][1])
DP=[[0 for _ in range(n)] for _ in range(n)]
for l in range(1,n):
    for i in range(n-l):
        j=i+l
        DP[i][j]=10**6
        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[0][-1])

Submission status: Accepted

Solution code:
n = int(input())

dimensions = []
for i in range(n):
    a, b = map(int, input().split())
    if i == 0:
        dimensions.append(a)
    dimensions.append(b)
inf = float('inf')
dps = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    dps[i][i] = 0
for i in range(n - 1, -1, -1):
    for j in range(i + 1, n):
        for k in range(i, j):
            dps[i][j] = min(dps[i][j],
                            dps[i][k] + dps[k + 1][j] + (dimensions[i] * dimensions[k + 1] * dimensions[j + 1]))
print(dps[0][n - 1])