Stone Game

Note the problem description in LintCode is different from LeetCode for "Stone Game". Here we discuss the LintCode version:

https://www.lintcode.com/problem/stone-game/description

Question

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:

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

Tags

Dynamic Programming

Related Problems

Hard Burst Balloons 29 %

Analysis

死胡同:容易想到的一个思路从小往大，枚举第一次合并是在哪? 转而用记忆化搜索的思路，从大到小，先考虑最后的0 ~ n-1合并的总花费。

Dynamic Programming

DP四要素

• State:

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

• Function:

  • 预处理sum[i,j]表示i到j所有石子价值和

  • dp[i][j] = min(dp[i][k]+dp[k+1][j]+sum[i,j]) 对于所有k属于{i,j}

• Intialize:

  • for each i

    • dp[i][i] = 0

• Answer:

  • dp[0][n-1]

区间型DP，利用二维数组下标表示下标范围。 需要注意的是对状态转移方程的理解，也就是对每一种分割方式进行遍历.

Divide & Conquer + Memoization

分割成子问题的思路在于用不同的pivot将原有的数组分割成为不同的区间，并且递归地每一个子区间重复同样的分割过程。

计算interval sum时，已知start和end，那么最好的方式就是预先生成一个prefix sum数组，这样区间和就可以用sum[end + 1] - sum[start + 1 - 1]来计算.

对于 interval sum ，根据搜索结构可以做一个显而易见的优化，因为每次 split 的 start, pivot, end 我们都知道，而且合并（start, end） 区间的两堆石子，最终的区间和一定为 (start, end) 的区间和，用一维的 prefix sum 数组就可以了。

用 prefix sum 数组要记得初始化时候的 int[n + 1] zero padding，还有取值时候对应的 sum[end + 1] - sum[start + 1 - 1] offset.

• 来源：https://mnmunknown.gitbooks.io/algorithm-notes/625,_dong_tai_gui_hua_ff0c_qu_jian_lei_dp.html

每次归并的 cost = 归并两个区间的最优 cost + 两个区间的区间和，即：

int cost = memoizedSearch(start, i, A, dp, sum) + memoizedSearch(i + 1, end, A, dp, sum) + sum[end + 1] - sum[start];

比较要注意的是循环pivot时数组的下标，以下两种实现方式都是可行的 (注意防止出现无限循环，即recursive调用搜索函数时，不能出现start, end又被当成输入的情况)：

i ~ [start, end - 1], => [start, i], [i + 1, end - 1]

for(int i = start; i < end; i++){
    int cost = memoizedSearch(start, i, A, dp, sum) + 
        memoizedSearch(i + 1, end, A, dp, sum) +
        sum[end + 1] - sum[start];
    min = Math.min(min, cost);
}

i ~ [start + 1, ... end], => [start, i - 1], [i, end]

for(int i = start + 1; i <= end; i++){
    int cost = memoizedSearch(start, i - 1, A, dp, sum) + 
        memoizedSearch(i, end, A, dp, sum) + 
        sum[end + 1] - sum[start];
    min = Math.min(min, cost);
}

Solution

DP - (252 ms)

public class Solution {

    /**
     * @param A an integer array
     * @return an integer
     */
    int search(int l, int r, int[][] f, int[][] visit, int[][] sum) {

        if(visit[l][r] == 1) {
            return f[l][r];
        }

        if(l == r) {
            visit[l][r] = 1;
            return f[l][r];
        }

        f[l][r] = Integer.MAX_VALUE;
        for (int k = l; k < r; k++) {
            f[l][r] = Math.min(f[l][r], search(l, k, f, visit, sum) + search(k + 1, r, f, visit, sum) + sum[l][r]);
        }

        visit[l][r] = 1;
        return f[l][r];
    }

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

        int n = A.length;

        // initialize
        int[][] f = new int[n][n];
        int[][] visit = new int[n][n];

        for (int i = 0; i < n; i++) {
            f[i][i] = 0;
        }

        // preparation
        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];
            }
        }

        return search(0, n-1, f, visit, sum);
    }
}

(Preferred) Divide and Conquer + Memoization (251 ms AC)

public class Solution {
    /**
     * @param A an integer array
     * @return an integer
     */
    public int stoneGame(int[] A) {
        // Write your code here
        if(A == null || A.length == 0) return 0;
        int n = A.length;

        // Minimum cost to merge interval dp[i][j]
        int[][] dp = new int[n][n];
        int[] sum = new int[n + 1];

        // Pre-process interval sum
        for(int i = 0; i < n; i++){
            sum[i + 1] = sum[i] + A[i];
        }

        return memoizedSearch(0, n - 1, A, dp, sum);
    }

    private int memoizedSearch(int start, int end, int[] A, int[][] dp, int[] sum){
        if(start > end) return 0;
        if(start == end) return 0;
        if(start + 1 == end) return A[start] + A[end];

        if(dp[start][end] != 0) return dp[start][end];

        int min = Integer.MAX_VALUE;
        for(int i = start; i < end; i++){
            int cost = memoizedSearch(start, i, A, dp, sum) + 
                memoizedSearch(i + 1, end, A, dp, sum) + 
                sum[end + 1] - sum[start];
            min = Math.min(min, cost);
        }

        dp[start][end] = min;

        return min;
    }
}

Reference

• Jiuzhang: Stone Game
• https://mnmunknown.gitbooks.io/algorithm-notes/625,_dong_tai_gui_hua_ff0c_qu_jian_lei_dp.html