Go: package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextInt()
	p := make([]int, N+1)
	dp := make([][]int, N+1)
	for i, _ := range dp {
		dp[i] = make([]int, N+1)
	}
	for i := 0; i < N; i++ {
		p[i] = sc.nextInt()
		p[i+1] = sc.nextInt()
	}
	for i := 1; i <= N; i++ {
		dp[i][i] = 0
	}
	for l := 2; l <= N; l++ {
		for i := 1; i <= N-l+1; i++ {
			j := i + l - 1
			dp[i][j] = 1 << 60
			for k := i; k <= j-1; k++ {
				dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j])
			}
		}
	}

	fmt.Fprintln(wtr, dp[1][N])
	wtr.Flush()
}

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

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

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

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

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

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

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

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

Python: import math

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

def init(p):
    global dp
    for i in range(1, n):
        dp[i][i+1] = p[i-1]*p[i]*p[i+1]

def solve(r, c):
    global dp
    smallest = math.inf
    for i in range(r, c):
        temp = p[r-1]*p[i]*p[c] + dp[r][i] + dp[i+1][c]
        if temp < smallest:
            smallest = temp
    return smallest

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

init(p)
for j in range(3, n+1):
    for i in range(j-2, 0, -1):
        dp[i][j] = solve(i, j)
print(str(dp[1][n]))