Go: package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	mm := make([]int, n+1)
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, n+1)
	}
	for i := 0; i < n; i++ {
		mm[i] = getNextInt(scanner)
		mm[i+1] = getNextInt(scanner)
	}

	for l := 2; l <= n; l++ {
		for i := 1; i <= n-l+1; i++ {
			j := i + l - 1
			for k := i; k <= j-1; k++ {
				d := dp[i][k] + dp[k+1][j] + mm[i-1]*mm[k]*mm[j]
				if dp[i][j] == 0 || dp[i][j] > d {
					dp[i][j] = d
				}
			}
		}
	}

	fmt.Fprintln(writer, dp[1][n])

	writer.Flush()
}

Python: # 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[j+1]*P[k+1], dp[i][j])
# from pprint import pprint
# pprint(dp)
print(dp[0][-1])

Python: import sys
sys.setrecursionlimit(10**7)
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

# n = int(input())
# a, b = map(int, input().split())
# int_list = list(map(int, input().split()))
# l = list(input().split())



def solve():
    n = int(input())
    mat_list = []
    for i in range(n):
        mat_list.append(list(map(int, input().split())))
    dprint(mat_list)

    # 掛け始めのidxと掛け終わりのidxをi, jとし、計算回数を持つメモ
    memo = [[0 for i in range(n)] for i in range(n)]

    def calc(start, end):
        dprint("*", start, end)
        # 1つの行列なら0
        if end == start:
            return 0

        # メモがあれば返す
        if memo[start][end] != 0:
            return memo[start][end]

        # 2つの行列なら、答えを計算しメモ追記
        if end - start == 1:
            cost = mat_list[start][0] * mat_list[start][1] * mat_list[end][1]
            memo[start][end] = cost
            dprint(start, end, cost)
            return cost

        # 3つ以上なら、再帰
        min_cost = -1
        if end - start >= 2:
            for right_start in range(start+1, end+1):
                left = calc(start, right_start-1)
                right = calc(right_start, end)
                cost = left + right + mat_list[start][0] * mat_list[right_start][0] * mat_list[end][1]
                if min_cost == -1 or min_cost > cost:
                    min_cost = cost
                dprint(start, end, right_start, min_cost, cost)

        memo[start][end] = min_cost
        return min_cost

    ans = calc(0, n-1)
    dprint(memo)
    print(int(ans))

solve()

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

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

Python: import sys

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

m = list(map(int, sys.stdin.readline().split()))
for _ in range(n-1):
    _, a = sys.stdin.readline().split()
    m.append(int(a))

c = [[-1 for _ in range(n)] for _ in range(n)]

def val(a, b):
    if a==b: return 0
    if c[a][b]>0: return c[a][b]
    c[a][b]=val(a+1,b)+m[a-1]*m[a]*m[b]
    for k in range(a+1, b):
        v=val(a,k)+val(k+1,b)+m[a-1]*m[k]*m[b]
        if c[a][b]>v: c[a][b]=v
    return c[a][b]

print(val(0, n-1))

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
    #pprint.pprint(mul)

    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)
        #pprint.pprint(mul)
    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()

Python: import sys

sys.setrecursionlimit(10**7)

inf = float('inf')

def solve():
    n = int(sys.stdin.readline())

    r = [0] * n
    c = [0] * n

    for i in range(n):
        ri, ci = map(int, sys.stdin.readline().split())
        r[i] = ri
        c[i] = ci

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

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

    ans = dp[0][n]

    print(ans)

if __name__ == '__main__':
    solve()

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

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

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