/**
 * 附上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;
}


Measured memory_bytes: 3116