Go: package main

import (
	"fmt"
	"bufio"
	"os"
	"strconv"
)

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n := nextInt(sc)

	P := make([]int, n+1)
	for i := 1; i <= n; i++ {
		l := nextInt(sc)
		P[i-1] = l
		m := nextInt(sc)
		P[i] = m
	}

	matrix := make([][]int, n+1)
	for i := 0; i < n+1; i++ {
		matrix[i] = make([]int, n+1)
	}

	for l := 2; l <= n; l++ {
		for i := 1; i <= n - l + 1; i++ {
			j := i + l - 1
			matrix[i][j] = (1 << 21)
			for k := i; k <= j-1; k++ {
				matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k+1][j] + P[i-1] * P[k] * P[j])
			}
		}
	}
	fmt.Println(matrix[1][n])
}

Python: n = int(input())
INF = 10**9
P = []
for i in range(n):
    p = map(int, input().split())
    P.append()
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 - 1][0] * p[k][1] * p[j][1])

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

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

Python: n = int(input())
P = []
for i in range(n):
    p = map(int, input().split())
    P.append()
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 - 1][0] * p[k][1] * p[j][1])

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

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

Python: n = int(input())
M = []
for _ in range(n):
    M.append([int(i) for i in input().split()])

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

print(martixChainMultipication(M)[0][n-1])

Python: #!/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))

Python: import sys, itertools

n = int(sys.stdin.readline())
MM = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

amin = 0
m = MM[0][:]
for i in range(n-1):
    amin += m[0]*m[1]*MM[i+1][1]
    m[1]=MM[i+1][1]


for t in itertools.permutations(range(n-1), n-2):

    mm=[m[:] for m in MM]
    o = list(t)
    ans=0
    for _ in range(n-2):
        i = o.pop(0)
        ans += mm[i][0]*mm[i+1][1]*mm[i][1]
        if ans>amin: break
        mm[i][1] = mm[i+1][1]
        mm.pop(i+1)
        
        for j in range(len(o)):
            if o[j]>i: o[j] -=1
    else:
        ans += mm[0][0]*mm[0][1]*mm[1][1]
        if amin>ans: amin=ans


print(amin)

Python: n = int(input())
INF = 10**9
P = []
for i in range(n):
    p = map(int, input().split())
    P.append()
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])

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

Python: #!/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))

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