Go: package main

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

type Matrix struct {
	r int // num of row
	c int // num of column
}

type Range struct {
	start int // index, inclusive
	end   int // index, inclusive
}

func calcMultiplication(x, y Matrix) (Matrix, int) {
	if x.c != y.r {
		panic("cannnot calculate")
	}
	return Matrix{x.r, y.c}, x.r * y.c * x.c
}

func calcMinMatrixChainMultiplication(matrices []Matrix, r Range, memo map[Range]int) (Matrix, int) {
	if v, ok := memo[r]; ok {
		return Matrix{matrices[0].r, matrices[len(matrices)-1].c}, v
	}
	if len(matrices) == 0 {
		panic("must not be empty")
	} else if len(matrices) == 1 {
		return matrices[0], 0
	} else if len(matrices) == 2 {
		return calcMultiplication(matrices[0], matrices[1])
	}

	var minCount int = math.MaxInt32

	for i := 0; i < len(matrices)-1; i++ {
		formerMatrices := matrices[:i+1]
		latterMatrices := matrices[i+1:]
		matF, countF := calcMinMatrixChainMultiplication(formerMatrices, Range{0, i}, memo)
		matL, countL := calcMinMatrixChainMultiplication(latterMatrices, Range{i + 1, len(matrices) - 1}, memo)
		_, countFL := calcMultiplication(matF, matL)
		count := countF + countL + countFL
		if count < minCount {
			minCount = count
		}
	}
	return Matrix{matrices[0].r, matrices[len(matrices)-1].c}, minCount
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n, _ := nextInt(sc)
	matrices := make([]Matrix, n)
	for i := 0; i < n; i++ {
		r, _ := nextInt(sc)
		c, _ := nextInt(sc)
		matrices[i] = Matrix{r, c}
	}
	memo := make(map[Range]int)
	_, resultCount := calcMinMatrixChainMultiplication(matrices, Range{0, len(matrices) - 1}, memo)
	fmt.Println(resultCount)
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

C++: /**
 * 附上C++做法, c++的cin和string真好用，比java理解起来难，但是操作起来舒服很多，
 * java的string是immutable的这点比较麻烦
 * 感觉c++跟其他所有面向对象语言都不太一样
 */
#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

#include <iostream>
#include <set>
#include <string>
#include <climits>

#include <iostream>
#include <set>
#include <string>
#include <climits>


/**
 * Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conversions.

In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.

Return true if and only if you can transform str1 into str2.



Example 1:

Input: str1 = "aabcc", str2 = "ccdee"
Output: true
Explanation: Convert 'c' to 'e' then 'b' to 'd' then 'a' to 'c'. Note that the order of conversions matter.
Example 2:

Input: str1 = "leetcode", str2 = "codeleet"
Output: false
Explanation: There is no way to transform str1 to str2.


Note:

1 <= str1.length == str2.length <= 10^4
Both str1 and str2 contain only lowercase English letters.


6
30 35
35 15
15 5
5 10
10 20
20 25
 */

#include <vector>
#include <unordered_map>

//矩阵连乘问题，递归方程采用课本P47的递归方程。
//与课本P47的程序相比，两者都是填m[][]的上三角，
//但本程序是横向填表，而课本程序是斜向填表。
//本程序按照 自底向上，自左向右 的顺序来计算m[][]的上三角。
//程序中有记录相应断开位置到s[][]。

#include <iostream>

using namespace std;

void MatrixChain(int, int[], int **);

void CalculateMin(int i, int j, int dimen[], int **dp);


//void MatrixChain(int n, int dimen[], int **dp) {
//    //以下双重循环对m[][]的上三角进行填表
//    //填表顺序为自底向上，自左向右
//    for (int i = n; i >= 1; i--) {//i表示行
//        for (int j = i; j <= n; j++) {//j表示列，因为只填上三角，所以j的初值为i
//            //以下按照矩阵连乘问题的递归公式来求每一个m[i][j]
//            if (i == j) {
//                cout << sizeof(dp) << endl;
//                cout << dp[i][j] << endl;
//                dp[i][j] = 0;
//                cout << dp[i][j] << endl;
//                cout << 44 << endl;
//
//            } else {
//                CalculateMin(i, j, dimen, dp);
//            }
//        }
//    }
//}

void matrixChain(int n, int dimen[], int **dp) {
    for (int len = 0; len <= n; ++len) {
        for (int i = 1; i + len <= n; ++i) {
            int j = i + len;
            if (i == j) {
                dp[i][j] = 0;
            } else {
                CalculateMin(i, j, dimen, dp);
            }
        }
    }
}


void CalculateMin(int i, int j, int dimen[], int **dp) {
    dp[i][j] = dp[i][i] + dp[i + 1][j] + dimen[i - 1] * dimen[i] * dimen[j];
    for (int k = i + 1; k < j; k++) {//k用于尝试不同的断开位置
        int curr = dp[i][k] + dp[k + 1][j] + dimen[i - 1] * dimen[k] * dimen[j];
        if (curr < dp[i][j]) {//当前k值作为Ai连乘到Aj的断开位置能获得更少计算量
            dp[i][j] = curr; //刷新最优值
            //pivot[i][j] = k;   //刷新相应断开位置
        }
    }
}

int main() {
    int n;
    cin >> n;
    int *tempP = new int[2 * n]; //dimen[0]为A1的行数；dimen[i]为Ai的列数
    int *dimen = new int[n + 1];    //dimen[0]为A1的行数；dimen[i]为Ai的列数
    int **dp = new int *[n + 1]; //dp[i][j]为Ai连乘到Aj的最少乘次数
    for (int i = 1; i <= n; i++) {
        dp[i] = new int[n + 1];
    }
    for (int i = 0; i < 2 * n; i++) {
        cin >> tempP[i];
    }
    for (int i = 0; i <= n; i++) {
        dimen[i] = i == 0 ? tempP[0] : tempP[i * 2 - 1];
    }
    matrixChain(n, dimen, dp);
    cout << dp[1][n] << endl; //最优值存储在m[1][n]
    return 0;
}

C++: #include<bits/stdc++.h>

using namespace std;

static const int N = 100;

//m[i][j]には、i～j番目までの行列のコストの最小値が入る。
int main(void){
    int n, p[N+1], m[N+1][N+1];
    cin >> n;
    //行列の行と列をpに入れる。i番目の行列の列とi+1番目の行列の行は同じ値なので同じ場所に入れてる
    for(int i = 1; i <= n; i++){
        cin >> p[i-1] >> p[i];
    }
    //i番目の行列とi番目の行列では計算が発生しないので0で初期化
    for(int i = 1; i <= n; i++)m[i][i] = 0;
    //連鎖行列積のコスト計算
    //lは対象とする行列の数を決めてる
    for(int l = 2; l <= n; l++){
        //i番目からj番目までの行列計算のコストを計算する。iとjはそのための変数
        //iは1番目の行列から、jが行列の存在する範囲を超えないようにi - l + 1番目までいく
        for(int i = 1; i <= n - l + 1; i++){
            //j = i + l だとi ~ jまでの範囲の行列の数が l + 1個になってしまうのでj = i + l - 1になっている。
            int j = i + l - 1;
            //めっちゃ小さい値で初期化
            m[i][j] = (1 << 21);
            //i番目からj番目までの最小コストを計算する。
            //(M1M2M3M4M5)の最小コストは、例えば(M1M2M3)(M4M5)だとすると、このときkは3。で、(M1M2M3)は(M1M2)(M3)と(M1)(M2M3)の小さいほうの値で、もう入ってる。
            //(M4M5)は一通りのコストしかないので、OK。
            //この時 m[1][5] = (M1M2M3)のコスト + (M4M5)のコスト + (前半の計算でできる行列) × (後半の計算で出来る行列)のコスト(M1の行数 * M3の列数 * M5の列数)
            for(int k = i; k <= j - 1; k++){
                m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i-1] * p[k] * p[j]);
            }
        }
    }
    cout << m[1][n] << endl;
    return 0;
}

C++: #include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int dp(vector<pair<int, int>> &dim, vector<vector<int>> &memo, int r, int l) {
  // dp[r][l] := [r,l)の区間の行列を掛けるときのスカラー乗算の最小値
  if (memo[r][l] != -1) {
    return memo[r][l];
  }
  if (l - r == 1) {
    return memo[r][l] = 0;
  }
  int res = INT32_MAX;
  for (int i = 1; i < l - r; i++) {
    res = min(res, dp(dim, memo, r, r + i) + dp(dim, memo, r + i, l) +
                       dim[r].first * dim[r + i].first * dim[l - 1].second);
  }
  return memo[r][l] = res;
}

int main() {
  int n;
  cin >> n;
  vector<pair<int, int>> dim(n);
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    dim[i] = make_pair(a, b);
  }
  vector<vector<int>> memo(n + 1, vector<int>(n + 1, -1));
  cout << dp(dim, memo, 0, n) << endl;
}

C++: #include <iostream>
using namespace std;
int n, a[111], b[111], dp[111][111];
int main() {
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
	for(int i = 2; i <= n; i++) {
		for(int j = 0; j <= n - i; j++) {
			int l = j, r = j + i; // [l, r)
			dp[l][r] = 999999999;
			for(int k = l + 1; k < r; k++) {
				dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + a[l] * b[r]);
			}
		}
	}
	cout << dp[0][n] << endl;
}