Stone Game II

Description

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.

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

Discussion

Method

DP 区间型

class Solution {
public:
    /**
     * @param A an integer array
     * @return an integer
     */
    int stoneGame2(vector<int>& A) {
        // Write your code here
        int n = A.size();
        if (n <= 1)
            return 0;
        vector<int> sum(2 * n + 1, 0);
        vector<vector<int> > dp(2 * n, vector<int>(2 * n, INT_MAX));

        sum[0] = 0;
        for (int i = 0; i < 2 * n; i++) {
            sum[i + 1] = sum[i] + A[i % n];
            dp[i][i] = 0;

        }

        for (int len = 2; len <= 2 * n; len++)
            for (int i = 0; i < 2 * n && i + len <= 2 * n; i++) {
                int j = i + len - 1;
                for ( int k = i; k < j; k++)
                    if (dp[i][k] + dp[k + 1][j] + sum[j + 1] - sum[i] < dp[i][j]) {
                        dp[i][j] = dp[i][k]+dp[k + 1][j] + sum[j + 1] - sum[i];
                }
            }
        int ans = INT_MAX;
        for (int i = 0; i < n; ++i)
            if (dp[i][i + n - 1] < ans)
                ans = dp[i][i + n - 1];
        return ans;
    }
};