There is a stone game.At the beginning of the game the player picks n piles of stonesin a circle.

The goal is to merge the stones in one pile observing the following rules:

At each step of the game,the player can merge two adjacent piles to a new pile.
The score is the number of stones in the new pile.
You are to determine the minimum of the total score.

Have you met this question in a real interview?

Yes

Example

For[1, 4, 4, 1], in the best solution, the total score is18:

1. Merge second and third piles =
>
 [2, 4, 4], score +2
2. Merge the first two piles =
>
 [6, 4]，score +6
3. Merge the last two piles =
>
 [10], score +10

Other two examples:
[1, 1, 1, 1]return8
[4, 4, 5, 9]return43

class Solution {

public:

/\*\*

 \* @param A an integer array

 \* @return an integer

 \*/

int stoneGame2\(vector<int>& A\) {

    // Write your code here

    if \(A.size\(\) < 1\) {

        return 0;

    }

    int n = A.size\(\);

    vector<vector<int>> dp\(2\*n, vector<int>\(2\*n, 0\)\);

    vector<vector<int>> sum\(2\*n, vector<int>\(2\*n, 0\)\);

    vector<vector<bool>> flag\(2\*n, vector<bool>\(2\*n, false\)\);



    for \(int i = 0; i < 2\*n; ++i\) {

        flag\[i\]\[i\] = true;

        int temp = 0;

        for \(int j = i; j < 2\*n && j <= i + n - 1 ; ++j\) {

            temp += A\[j % n\];

            sum\[i\]\[j\] = temp;

        }

    }



    int minScore = INT\_MAX;

    for \(int i = 0; i < n; ++i\) {

        int temp = search\(i, i + n - 1, sum, dp, flag\);

        // cout << " i : " << i <<endl;

        minScore = min\(minScore, temp\);

        // cout << "minScore : " << minScore<< endl;

    }

    return minScore;

}

private:

int search\(int left, int right, vector<vector<int>>& sum, 

           vector<vector<int>>& dp, vector<vector<bool>>& flag\)

{

    if \(flag\[left\]\[right\]\) {

        return dp\[left\]\[right\];

    }

    int minScore = INT\_MAX;

    for \(int k = left; k < right; ++k\) {

        int leftScore = search\(left, k, sum, dp, flag\);

        int rightScore = search\(k + 1, right, sum, dp, flag\);

        int curScore = leftScore + rightScore + sum\[left\]\[right\];

        minScore = min\(minScore, curScore\);

    }

    dp\[left\]\[right\] = minScore;

    flag\[left\]\[right\] = true;

    return minScore;

}

};