Problem

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

思路

• 画搜索树,
• 图左边
  • 按照每个合并的可能性来, 从而合并成大的数值. 这种方法即使用记忆化搜索, 能够合并的状态也很小
  • 所以我们不直接将两个值合并, 而是将连续的值划分成一个一个区间, 这样子用区间作为状态, 相同的区间便能很好地进行记忆化

• 图右边

  • 合并区间, 对这区间合并的花费进行记忆化.

  • 从大到小思考, 先考虑最后的 0 到 n - 1 的总花费 是由哪些小区间组成的

    

• 为什么要用区间型dp ?

  • because we can merge two stone at any interval in the array, we need two indexes to record where this interval begins and ends.

• state

  • dp[i]:代表把第i个到第j个石子合并到一起的最小花费

• function

  • dp[i][j] = min{ dp[i][k] + dp[k + 1][j] + sum[i][j] } i <= k <= j

• initialize (这是我出错的地方, 初始化不应该是stone[i], 而是0. 原因是 第i个和第i个合并花费就是0)

  • dp[i][i] = 0
  • i <= j

• answer

  • dp[0][n - 1]

• 注意:

  • 同样需要对sum进行区间型动态规划, i <= j,
  • 这道题不能用for循环来做, 因为蓝色依赖于绿色
  • 

    public int stoneGame(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int len = A.length;
        boolean[][] visited = new boolean[len][len];
        int[][] dp = new int[len][len];
        int[][] sum = new int[len][len];
        for (int i = 0; i < len; i++) {
            sum[i][i] = A[i];
            for (int j = i + 1; j < len; j++) {
                sum[i][j] = sum[i][j - 1] + A[j];
            }
        }

        return getScorefrom(A, 0, len - 1, dp, visited, sum);
    }

    private int getScorefrom(int[] A, int i, int j, int[][] dp, boolean[][] visited, int[][] sum) {
        if (visited[i][j]) {
            return dp[i][j];
        }

        visited[i][j] = true;

        if (i == j) {
            dp[i][j] = 0;
        } else {
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], getScorefrom(A, i, k, dp, visited, sum) 
                                    + getScorefrom(A, k + 1, j, dp, visited, sum)
                                    + sum[i][j]);
            }
        }
        return dp[i][j];
    }