Question

from lintcode
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

Idea

As explained in code comments.

/**
 *  The score of the last-time merge which turns stones from position i to j into ONE pile,
 *  is exactly sum(stones from i to j)
 *
 *  Before the last-time merge, from pos i to j,
 *  let x be an arbitary stone pos between i and j, then
 *  a merge from i to x-1
 *  and a merge from x to j
 *  must have happened already
 *
 *  To get the minimum score, we have to make the total score
 *  acquired in `merging i to x-1`, and `merging x to j`, to be minimized
 *
 *  let f[i][j] be the minimum score you can get by merging stones from pos i to pos j, then
 *  f(i, j) = sum(i,j) + min(f(i, x-1) + f(x, j)) where i < x <= j
 */
public class Solution {
    /*
     * @param A: An integer array
     * @return: An integer
     */
    public int stoneGame(int[] stones) {
        if (stones.length == 0) return 0;
        // f[i][j] means the minimum score you can get by merging stones from pos i to pos j
        int[][] minScore = new int[stones.length][stones.length];
        int[][] sum = new int[stones.length][stones.length];

        /**
         *  sum[i][j] is the sum from stones[i] to stones[j]
         */
        // take each index as left start point
        for (int left = 0; left < stones.length; left++) {
            // calculate its right end point
            for (int right = left; right < stones.length; right++) {
                // perform sum operation
                sum[left][right] = left == right
                        ? stones[left]
                        : sum[left][right - 1] + stones[right];
            }
        }

        // iterate length of [i to j], from length = 1 to N
        // why iterate by ascending length? look at the DP formula
        // f(i, j) = sum(i,j) + min(f(i, x-1) + f(x, j)) where i < x <= j
        // to calculate f(i,j), all of scopes that is within (i,j) has to be calculated first
        // i.e. to calculate a scope of specific length,
        // all of its sub-scopes with smaller lengths must be calculated first
        for (int len = 1; len <= stones.length; len++) {
            // use each position as start point, get the end point by the fixed length
            for (int i = 0; i + len - 1 < stones.length; i++) {
                // length = 1, no merge, no score
                if (len == 1)
                    minScore[i][i] = 0;
                else {
                    int endIndex = i + len - 1;
                    // see getMinScore() for details
                    minScore[i][endIndex] = getMinScore(i, endIndex , sum, minScore,stones);
                }
            }
        }

        return minScore[0][stones.length - 1];
    }

    // f(i, j) = sum(i,j) + min(f(i, x-1) + f(x, j)) where i < x <= j
    private int getMinScore(int i, int endIndex, int[][] sum, int[][] minScore, int[] stones) {
        int score = Integer.MAX_VALUE;
        for (int x = i + 1; x <= endIndex; x++) {
            score = Math.min(
                    score,
                    minScore[i][x -1] + minScore[x][endIndex] +
                    sum[i][endIndex]
            );
        }
        return score;
    }
}