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
	}

	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
		}
	}
	memo[r] = minCount
	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++: /**
 * 	matrix chain multiplication
 * 	f(n,m) = multiply Mn*M(n+1)*...*M(m-1)*M(m)
 * 	f(n,n) = 1
 * 	r(n)=c(n-1)
 * 	f(n,n+1) = C(n) * R(n) * C(n+1) = c(n) * c(n-1) * c(n+1)
 * 	f(n,k,m) = f(n,k)*f(k+1,m)*C(n)*r(n)*c(k)
 * 	f(n,m) = min(f(n,k,m)
 */

#include <iostream>
#include <cmath>
#include <climits>

using namespace std;

int r[45] = {0};
int a[100][100] = {0};

int f(int n, int m);
int f(int n, int k, int m);


int f(int n, int k, int m)
{
	return f(n,k) + f(k+1,m) + (r[n] * r[k+1] * r[m+1]);
}

int f(int n, int m)
{
	if (n==m) return 0;
	int & ra = a[n][m];
	if (ra) return ra;
	ra = INT_MAX;
	for (int k=n;k<m;k++)
	{
		int ans = f(n,k,m);
		if (ans < ra) ra = ans;
	}
	return ra;
}

int main()
{
	int rr = 0;
	int cc = 0;
	int n = 0;
	cin >> n;
	for (int i=0;i<n;i++)
	{
		cin >> rr >> cc;
		r[i]=rr;
		r[i+1]=cc;
	}
	for (int i=0;i<n-1;i++)
	{
		a[i][i+1] = r[i] * r[i+1] * r[i+2];
	}
	int ans = f(0,n-1);
	cout << ans << endl;
}

C++: #include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
const int MAX_V = 100;
vector<pair<int,int> > pairs;
int main(){
  int n; scanf("%d",&n);
  for(int i=0;i<n;i++){
    pair<int,int> p;
    scanf("%d %d",&p.first,&p.second);
    pairs.push_back(p);
  }
  long long int sum=0;
  while(pairs.size()>1){
    vector<pair<int,int> >::iterator min_ptr;
    int min=0x7fffffff;
    int mulMin=0x7fffffff;
    for(auto iter=pairs.begin()+1;iter<pairs.end();iter++){
      int localMin = (*(iter-1)).first;
      if(localMin > (*iter).second) localMin = (*iter).second;
      int mul=(*(iter-1)).first*(*iter).second;
      if(min>=localMin){
	if(mulMin>mul){
	  min=localMin;
	  mulMin=mul;
	  min_ptr=iter;
	}
      }
    }
    cout<<(*(min_ptr-1)).first<<":"<<(*min_ptr).first<<":"<<(*min_ptr).second<<"\n";
    sum+=(*(min_ptr-1)).first*(*min_ptr).first*(*min_ptr).second;
    (*(min_ptr-1)).second=(*min_ptr).second;
    pairs.erase(min_ptr);
  }
  printf("%lld\n",sum);
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <algorithm>

typedef long long ll;
const ll MOD = 1e9 + 7;
const long long INF = 1LL<<60;
const double PI=3.14159265358979323846;
const int NMAX=100005;
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<ll> r(n),c(n);
    for(int i = 0; i < n; i++){
        cin >> r[i] >> c[i];
    }
    ll dp[n+1][n+1];
    pair<ll,ll> rc[n+1][n+1];
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            dp[i][j] = INF;
        }
    }

    for(int l = 1; l <= n; l++){
        for(int i = 0; i < n; i++){
            int j = i+l;
            if(j > n) break;
            if(i+1 == j){
                dp[i][j] = 0;
                rc[i][j] = make_pair(r[i],c[i]);
            }
            for(int mid = i; mid <= j; mid++){
                ll tmp = dp[i][j];
                dp[i][j] = min(dp[i][j], dp[i][mid]+dp[mid][j]+rc[i][mid].first*rc[mid][j].second*rc[i][mid].second);
                if(dp[i][j] != tmp){
                    rc[i][j] = make_pair(rc[i][mid].first,rc[mid][j].second);
                }
            }
        }
    }

    cout << dp[0][n] << endl;

    return 0;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
static const int N = 100;
int main() {
	int n, p[N + 1], m[N + 1][N + 1];
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> p[i - 1] >> p[i];
	for (int i = 1; i <= n; i++)m[i][i] = 0;
	for (int l = 2; l <= n; l++) {
		for (int i = 1; i <= n - l + 1; i++) {
			int j = i + l - 1;
			m[i][j] = (1 << 21);
			for (int k = i; k <= j - 1; k++) {
				m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + m[k + 1][j] + p[i - 1] * p[k] * p[j]);
			}
		}
	}
	cout << m[1][n] << endl;
	return 0;
}

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

static const int N=100;

int main(){
  int n,p[N+1],m[N+1][N+1];
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>p[i-1]>>p[i];
  }
  for(int i=1;i<=n;i++)m[i][i]=0;
  for(int l=2;l<=n;l++){
    for(int i=1;i<=n-l+1;i++){
      int j=i+l-1;
      m[i][j]=(1<<21);
      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<bits/stdc++.h>
using namespace std;
struct matrix{
	long long x,y;
}m[110];
int n;
long long dp[110][110];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&m[i].x,&m[i].y);
	}
	for(int i=1;i<=n;i++){
		dp[i][i]=0;
	}
	for(int l=2;l<=n;l++){
		for(int i=1;i<=n-l+1;i++){
			int j=i+l-1;
			dp[i][j]=1<<20;
			for(int k=i;k<j;k++){
			    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+m[i].x*m[k].y*m[j].y);
			}
		}
	}
	//cout<<"i: "<<i<<" j: "<<j<<" dp: "<<dp[i][j]<<endl; 
	printf("%lld\n",dp[1][n]);
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<int> size(n+1);
	int r,c;
	for (int i=0;i<n;++i)
	{
		cin >> r >> c;
		size[i]=r;
	}
	size[n]=c;

	vector<vector<int>> m(n+1,vector<int>(n+1));
	const int infinity=32768*32767;

	// length=2
	for (int i=0;i<=n-(2-1);++i)
	{
		m[i][i+1]=0;
	}

	// length=3
	for (int i=0;i<=n-(3-1);++i)
	{
		m[i][i+2]=size[i]*size[i+1]*size[i+2];
	}

	// length>=4
	for (int i=4;i<=n+1;++i)
	{
		for (int j=0;j<=n-(i-1);++j)
		{
			int minimum=infinity;
			for (int k=1;k<=i-2;++k)
			{
				int sum=m[j][j+k]+m[j+k][j+i-1]+size[j]*size[j+k]*size[j+i-1];
				minimum=min(minimum,sum);
			}
			m[j][j+i-1]=minimum;
		}
	}

	cout << m[0][n] << endl;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
 
static const int N = 100;
 
int main() {
  int n, p[N+1], m[N+1][N+1];
  cin >> n;
  for ( int i = 1; i <= n; i++ ) {
    cin >> p[i - 1] >> p[i];
  }
 
  for ( int i = 1; i <= n; i++ ) m[i][i] = 0;
  for ( int l = 2; l <= n; l++ ) {
    for( int i = 1; i <= n -l +1; i++ ) {
      int j = i + l -1;
      m[i][j] = (1 << 21);
      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;
}