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

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.

Have you met this question in a real interview?  Yes 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

题目思路：

这题提示用dp解。可以想到，用dp[i][j]来表示合并stone i ~ j所得的最小score，那么求得dp[0][A.size() - 1]就为最后的答案了。那么怎么求dp[i][j]呢？题目是merge score，可以反向思考：每一个merge以后的stone，它是怎么被merge的？它一定是找了两个merge代价最小的stone来merge的。那么可以得到dp的方程为：dp[i][j] = dp[i][k] + dp[k + 1][j] + presum[i][j]。这里presum[i][j]是指在A中i~j所有元素的和；k从i到j - 1遍历，找出所有k中得到的最小dp[i][j]，就是最终所求的dp[i][j]. 从dp方程中也可以看出，决定dp[i][j]的并不是stone本身的value（因为presum[i][j]是不变的），而是上一次左右两边的stone各自merge时产生的不同score。

这里为了降低time cost，引入了visited matrix，去记录已经算过的dp[i][j]；否则会超时。

Mycode（AC = 218ms）：

class Solution { public: /** * @param A an integer array * @return an integer */ int stoneGame(vector<int>& A) { // Write your code here if (A.size() == 0) return 0; // initialize vectors vector<vector<int>> dp(A.size(), vector<int>(A.size(), INT_MAX)); vector<vector<bool>> visited(A.size(), vector<bool>(A.size(), false)); vector<vector<int>> presum(A.size(), vector<int>(A.size(), 0)); // get the value of presum matrix for (int i = 0; i < A.size(); i++) { presum[i][i] = A[i]; for (int j = i + 1; j < A.size(); j++) { presum[i][j] = presum[i][j - 1] + A[j]; } } stoneGame(dp, presum, visited, A, 0, A.size() - 1); return dp[0][A.size() - 1]; } void stoneGame(vector<vector<int>>& dp, vector<vector<int>>& presum, vector<vector<bool>>& visited, vector<int>& A, int start, int end) { // use visited matrix to mark whether // dp[start][end] is already computed // to save cost if (visited[start][end] || start > end) { return; } visited[start][end] = true; if (start == end) { dp[start][end] = 0; } else { for (int i = start; i < end; i++) { stoneGame(dp, presum, visited, A, start, i); stoneGame(dp, presum, visited, A, i + 1, end); // the score of start ~ end stone is equal to // previous scores of two parts + stone values from start to end dp[start][end] = min(dp[start][end], presum[start][end] + dp[start][i] + dp[i + 1][end]); } } } };