# 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 + 两个区间的区间和，即：

```java
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]`

```java
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]`

```java
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)

```java
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)**

```java
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://github.com/aaronice/lintcode/tree/bbbb974440d4233e80bad25778c3733867e871db/dynamic_programming/www.jiuzhang.com/solutions/stone-game/README.md)
* <https://mnmunknown.gitbooks.io/algorithm-notes/625,_dong_tai_gui_hua_ff0c_qu_jian_lei_dp.html>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/dynamic_programming/stone_game.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.