Stone Game

There is a stone game.At the beginning of the game the player picksnpiles of stones in a line.

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

1. At each step of the game,the player can merge two adjacent piles to a new pile.
2. The score is the number of stones in the new pile.

You are to determine the minimum of the total score.
Example

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

1. Merge second and third piles =>[4, 2, 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

S: 区间类DP， 由大到小进行记忆化搜索 O(n^3)

minSum[i][j]表示将i到j的石子分两堆合并能得到的最小值，则

minSum[i][j] = min(minSum[i][k] + minSum[k+1][j]) + sum[i][j], sum[i][j]为i到j石子的数值之和

class Solution {
public:
    int stoneGame(vector<int>& A) {
        int n = A.size();
        if (n < 2) return 0;
        preSum = vector<int>(n, 0);
        minSum = vector<vector<int>>(n, vector<int>(n, INT_MAX));
        visited = vector<vector<bool>>(n, vector<bool>(n, false));
        preSum[0] = A[0];
        for (int i = 1; i < n; ++i) {
            preSum[i] = preSum[i-1] + A[i];
        }
        return dfs(A, 0, n-1);
    }
    int dfs(vector<int>& A, int i, int j) {
        if (i >= j) {
            return 0;
        }
        if (visited[i][j]) {
            return minSum[i][j];
        }
        int curMin = 0;
        for (int k = i; k < j; ++k) {
            curMin = dfs(A, i, k);
            curMin += dfs(A, k + 1, j);
            if (i == 0) {
                curMin += preSum[j];
            } else {
                curMin += preSum[j] - preSum[i-1];
            }
            if (curMin < minSum[i][j]) {
                minSum[i][j] = curMin;
            }
        }
        visited[i][j] = true;
        return minSum[i][j];
    }

private:
    vector<int> preSum;
    vector<vector<int>> minSum;
    vector<vector<bool>> visited;
};

Stone Game II

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

S: 复制得到两倍长度，然后按上题求解

得到2n范围内的解，再循环遍历得到i到i+n-1范围的解

class Solution {
public:
    int stoneGame2(vector<int>& A) {
        int n = A.size();
        if (n < 2) return 0;
        preSum = vector<int>(2 * n, 0);
        minSum = vector<vector<int>>(2 * n, vector<int>(2 * n, INT_MAX));
        visited = vector<vector<bool>>(2 * n, vector<bool>(2 * n, false));
        preSum[0] = A[0];
        for (int i = 1; i < 2 * n; ++i) {
            preSum[i] = preSum[i-1] + A[i%n];
        }
        dfs(A, 0, 2 * n - 1);
        int result = INT_MAX;
        for (int i = 0; i < n; ++i) {
            if (minSum[i][i+n-1] < result) {
                result = minSum[i][i+n-1];
            }
        }
        return result;
    }
    int dfs(vector<int>& A, int i, int j) {
        if (i >= j) {
            return 0;
        }
        if (visited[i][j]) {
            return minSum[i][j];
        }
        int curMin = 0;
        int sum;
        if (i == 0) {
            sum = preSum[j];
        } else {
            sum = preSum[j] - preSum[i-1];
        }
        for (int k = i; k < j; ++k) {
            curMin = dfs(A, i, k);
            curMin += dfs(A, k + 1, j);
            if (curMin < minSum[i][j]) {
                minSum[i][j] = curMin;
            }
        }
        minSum[i][j] += sum;
        visited[i][j] = true;
        return minSum[i][j];
    }

private:
    vector<int> preSum;
    vector<vector<int>> minSum;
    vector<vector<bool>> visited;
};

312. Burst Balloons

Givennballoons, indexed from0ton-1. Each balloon is painted with a number on it represented by arraynums. You are asked to burst all the balloons. If the you burst ballooniyou will getnums[left] * nums[i] * nums[right]coins. Hereleftandrightare adjacent indices ofi. After the burst, theleftandrightthen becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:
(1) You may imaginenums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤n≤ 500, 0 ≤nums[i]≤ 100

Example:

Given[3, 1, 5, 8]

Return167

nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

S1: 记忆化搜索，同stone game

S2：由小区间到大区间dp O(n^n)

状态：dp[i][j]表示引爆i-j的气球能得到的最大值

状态转移方程: 假设i - j中最后引爆的是k (i <= k <= j)

valueK = num[i-1]*num[k]*num[j+1]

dp[i][j] = max(dp[i][j], dp[i][k-1] + valueK + dp[k+1][j])

初始化:当区间长度为1时，dp[i][i] = num[i-1]*num[i]*num[i+1]

结果: dp[0][n-1]

为了避免首尾的coner case，将dp数组的长度扩大两位，首尾各加一

    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<vector<int>> dp(n + 2, vector<int>(n + 2));
        int pre, next;
        for (int len = 1; len <= n; ++len) {
            for (int left = 1; left <= n - len + 1; ++left) {
                int right = left + len - 1;
                for (int k = left; k <= right; ++k) {
                    pre = left == 1? 1 : nums[left - 2];
                    next = right == n? 1 : nums[right];
                    int val = pre * nums[k - 1] * next;
                    dp[left][right] = max(dp[left][right], dp[left][k - 1] + val + dp[k + 1][right]);
                }
            }
        }
        return dp[1][n];
    }