Stone Game

There is a stone game.At the beginning of the game the player picks n piles of stones in a line.

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 [4, 1, 1, 4], in the best solution, the total score is 18:

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] return 8

[4, 4, 5, 9] return 43

Solutions:

1. 区间类DP，从大区间到小区间
2. State: dp[i][j] 区间（i, j）上最小的cost
3. Function: 大区间划分为小区间 dp[i][j] = min(d[i][k] + dp[k+1][j] + sum[i][j]) k from i to j-1. 其中的sum[i][j]为最后合并时候花费的cost，它是一定的
4. Initial: sum[i][j], d[i][i] = 0
5. Answer: dp[0][n-1]

    public int stoneGame(int[] A) {
        if(A == null || A.length <= 1) {
            return 0;
        }

        int n = A.length;

        int[][] sum = new int[n][n];
        for (int i = 0; i < n; ++i) {
            sum[i][i] = A[i];
            for (int j = i+1; j < n; ++j) {
                sum[i][j] = sum[i][j-1]+A[j];
            }
        }

        int[][] dp = new int[n][n];
        boolean[][] flag = new boolean[n][n];

        return search(0, n-1, dp, flag, sum);
    }

    private int search(int l, int r, int[][] dp, boolean[][] flag, int[][] sum) {
        if (l >= r) {
            return 0;
        }

        if (flag[l][r]) {
            return dp[l][r];
        }

        flag[l][r] = true;

        for (int k = l; k < r; ++k) {
            int value = search(l, k, dp, flag, sum) + search(k+1, r, dp, flag, sum) + sum[l][r];
            if (dp[l][r] == 0 || dp[l][r] > value) {
                dp[l][r] = value;
            }
        }

        return dp[l][r];
    }