ere is a stone game.At the beginning of the game the player picksnpiles 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 is18:
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]return8[4, 4, 5, 9]return43
line 40 recursive function call name
line 29 use vector
>
A as parameter , don't need A and A type should be vector
class Solution {
public:
/**
* @param A an integer array
* @return an integer
*/
int stoneGame(vector<int>& A) {
// Write your code here
if (A.empty()) {
return 0;
}
int n = A.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
vector<vector<int>> sum(n, vector<int>(n, 0));
vector<vector<bool>> flag(n, vector<bool>(n, false));
for (int i = 0; i < n; ++i) {
int val = 0;
for (int j = i; j < n; ++j) {
val += A[j];
sum[i][j] = val;
}
}
return dfs(0 , n - 1, dp, flag, sum);
}
private:
int dfs(int i, int j, vector<vector<int>>& dp, vector<vector<bool>>& flag,
vector<vector<int>>& sum) {
if (flag[i][j]) {
return dp[i][j];
}
if (i == j) {
flag[i][j] = true;
return 0;
}
int minCost = INT_MAX;
for (int k = i; k < j; ++k) {
int tempCost = sum[i][j] + dfs(i, k, dp, flag, sum) + dfs(k + 1, j, dp, flag, sum);
minCost = min(minCost, tempCost);
}
dp[i][j] = minCost;
flag[i][j] = true;
return dp[i][j];
}
};