> For the complete documentation index, see [llms.txt](https://luj.gitbook.io/code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://luj.gitbook.io/code/dynamic-programming/5-interval-dp/stone-game.md).

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

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

**Example 1:**

```
Input: [3, 4, 3]
Output: 17
```

**Example 2:**

```
Input: [4, 1, 1, 4]
Output: 18
Explanation:
  1. Merge second and third piles => [4, 2, 4], score = 2
  2. Merge the first two piles => [6, 4]，score = 8
  3. Merge the last two piles => [10], score = 18
```

## Note

贪心反例：\[6,4,4,6]\
死胡同：容易想到的一个思路从小往大，枚举第一次合并是在哪？

记忆化搜索的思路，从大到小，先考虑最后的0-n-1 合并的总花费

• 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-1}

• Intialize: For each i that dp\[i]\[i] = 0

• Answer: dp\[0]\[n-1]

总结：区间动态规划

* 设定状态: f\[i]\[j] 表示合并原序列 \[i, j] 的石子的最小分数
* 状态转移:`f[i][j] = min{f[i][k] + f[k+1][j]} + sum[i][j], sum[i][j] 表示原序列[i, j]区间的重量和`
* 边界:`f[i][i] = sum[i][i], f[i][i+1] = sum[i][i+1]`
* 答案:`f[0][n-1]`

## Code

```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 len = A.length;
        int[][] dp = new int[len][len];
        int[][] visited = new int[len][len];

        for (int i = 0; i < len; i++) {
            dp[i][i] = 0;
        }

        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 dfs(0, len - 1, dp, visited, sum);
    }

    private int dfs(int start, int end, 
                    int[][] dp, int[][] visited, int[][] sum) {
        if (start >= end) {
            visited[start][end] = 1;
            return dp[start][end];
        }                    

        if (visited[start][end] == 1) {
            return dp[start][end];
        }

        dp[start][end] = Integer.MAX_VALUE;
        for (int k = start; k < end; k++) {
            dp[start][end] = Math.min(dp[start][end], 
                                      dfs(start, k, dp, visited, sum) +
                                      dfs(k + 1, end, dp, visited, sum) +
                                      sum[start][end]);
        }

        visited[start][end] = 1;
        return dp[start][end];
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

```
GET https://luj.gitbook.io/code/dynamic-programming/5-interval-dp/stone-game.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.