1563. 石子游戏 V - 力扣（LeetCode）
题目
几块石子排成一行，每块石子都有一个关联值，关联值为整数，由数组stoneValue给出。
游戏中的每一轮：Alice 会将这行石子分成两个非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。
只剩下一块石子时，游戏结束。Alice 的分数最初为0。
返回Alice 能够获得的最大分数。
示例 1：
输入：stoneValue = [6,2,3,4,5,5]输出：18解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。 在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。 最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。
示例 2：
输入：stoneValue = [7,7,7,7,7,7,7]输出：28
示例 3：
输入：stoneValue = [4]输出：0
提示：
1 <= stoneValue.length <= 5001 <= stoneValue[i] <= 106
思路
- 神了这题目写的真的有点迷惑，纯看文字没注意看括号都没发现是把一排石子分成左右两边，想了半天都没想到一个好一点的复杂度的解法，原来是divide不是select（跪了）。
- 题目理解了就能开始做了，一拍脑袋想不到什么哪种选择策略可以保证最终分数一定是最高的，所以只能无脑穷举了。
- 直接可以想到的方法就是做递归，每层递归做一件事情，遍历所以空，来一刀，然后左右分块继续向下递归，直到只剩一个数字为止，返回最后的总得分，然后取最大的一个即可（这个如果用python来做切片的话挺方便的，C++的话貌似还得勤勤恳恳赋一下值，偷个懒传引用就好了），代码如下：
class Solution { public: int countSum(vector<int>& stoneValue, int start, int end) { int sum = 0; for(int i = start; i <= end; i++) sum += stoneValue[i]; return sum; } int getMaxScore(vector<int>& stoneValue, int start, int end) { if(start == end) return 0; int leftSum = 0, rightSum = 0, maxScore = 0, currentScore = 0, leftScores = 0, rightScores = 0; for(int i = start; i < end; i++) { leftSum = countSum(stoneValue, start, i); rightSum = countSum(stoneValue, i+1, end); currentScore = min(leftSum, rightSum); if(leftSum < rightSum) maxScore = max(maxScore, currentScore+getMaxScore(stoneValue, start, i)); else if(leftSum > rightSum) maxScore = max(maxScore, currentScore+getMaxScore(stoneValue, i+1, end)); else { maxScore = max(maxScore, currentScore+getMaxScore(stoneValue, start, i)); maxScore = max(maxScore, currentScore+getMaxScore(stoneValue, i+1, end)); } } return maxScore; } int stoneGameV(vector<int>& stoneValue) { return getMaxScore(stoneValue, 0, stoneValue.size()-1); } };- 显然这样的方法随着递归层数的增加效果是非常差的，最差估计能接近O(2^n)。
- 可以注意到递归的过程中发生了多次的重复计算，根据智能分析的建议和较优复杂度情况，可以采用记忆化存储的方式，设置n*n的状态数组v，v[i][j]表示从i到j这个区间的最大得分，调用的过程中先查查这个得分是否被计算了，若已经被计算就直接赋值即可。
class Solution { public: int countSum(vector<int>& stoneValue, int start, int end) { int sum = 0; for(int i = start; i <= end; i++) sum += stoneValue[i]; return sum; } int getMaxScore(vector<vector<int>>& partialValue,vector<int>& stoneValue, int start, int end) { if(start == end) { partialValue[start][end] = 0; return 0; } int leftSum = 0, rightSum = 0, maxScore = 0, currentScore = 0, leftScores = 0, rightScores = 0; for(int i = start; i < end; i++) { leftSum = countSum(stoneValue, start, i); rightSum = countSum(stoneValue, i+1, end); currentScore = min(leftSum, rightSum); if(leftSum < rightSum) { if(partialValue[start][i] == -1) partialValue[start][i] = getMaxScore(partialValue, stoneValue, start, i); maxScore = max(maxScore, currentScore+partialValue[start][i]); } else if(leftSum > rightSum) { if(partialValue[i+1][end] == -1) partialValue[i+1][end] = getMaxScore(partialValue, stoneValue, i+1, end); maxScore = max(maxScore, currentScore+partialValue[i+1][end]); } else { if(partialValue[start][i] == -1) partialValue[start][i] = getMaxScore(partialValue, stoneValue, start, i); maxScore = max(maxScore, currentScore+partialValue[start][i]); if(partialValue[i+1][end] == -1) partialValue[i+1][end] = getMaxScore(partialValue, stoneValue, i+1, end); maxScore = max(maxScore, currentScore+partialValue[i+1][end]); } } return maxScore; } int stoneGameV(vector<int>& stoneValue) { int len = stoneValue.size(); vector<vector<int>> partialValue(len, vector<int>(len, -1)); return getMaxScore(partialValue, stoneValue, 0, len-1); } };- 结果还是超时了，最后分析之后发现countSum行为才是大量重复计算的根源，直接改成前缀和计算能节省大量的时间开销。
代码实现
class Solution { public: int countSum(vector<int>& stoneValue, int start, int end) { int sum = 0; for(int i = start; i <= end; i++) sum += stoneValue[i]; return sum; } int getMaxScore(vector<vector<int>>& partialValue,vector<int>& stoneValue, int start, int end) { if(start == end) { partialValue[start][end] = 0; return 0; } int leftSum = 0, rightSum = 0, maxScore = 0, currentScore = 0, leftScores = 0, rightScores = 0; rightSum = countSum(stoneValue, start, end); for(int i = start; i < end; i++) { leftSum += stoneValue[i]; rightSum -= stoneValue[i]; currentScore = min(leftSum, rightSum); if(leftSum < rightSum) { if(partialValue[start][i] == -1) partialValue[start][i] = getMaxScore(partialValue, stoneValue, start, i); maxScore = max(maxScore, currentScore+partialValue[start][i]); } else if(leftSum > rightSum) { if(partialValue[i+1][end] == -1) partialValue[i+1][end] = getMaxScore(partialValue, stoneValue, i+1, end); maxScore = max(maxScore, currentScore+partialValue[i+1][end]); } else { if(partialValue[start][i] == -1) partialValue[start][i] = getMaxScore(partialValue, stoneValue, start, i); maxScore = max(maxScore, currentScore+partialValue[start][i]); if(partialValue[i+1][end] == -1) partialValue[i+1][end] = getMaxScore(partialValue, stoneValue, i+1, end); maxScore = max(maxScore, currentScore+partialValue[i+1][end]); } } return maxScore; } int stoneGameV(vector<int>& stoneValue) { int len = stoneValue.size(); vector<vector<int>> partialValue(len, vector<int>(len, -1)); return getMaxScore(partialValue, stoneValue, 0, len-1); } };复杂度分析
时间复杂度：因为会考虑所有区间，区间总数为n(n+1)/2=O(n^2)，再加上每个区间会进行一次比那里，长度为O(L)，不妨近似为O(n)——所以总的时间复杂度应该是O(n^3)。
空间复杂度：O(n^2)——引入了记忆化存储的n*n的数组，其余开销为栈开销，最坏是O(n)。
知识积累
- vector初始化(以二层为例)：vector<vector<int>> 变量名(外层长度, vector<int>(内层长度, 初始值));
- vector初始化的另一种形式：变量名.assign(外层长度, vector<int>(内层长度))——估计默认值为0.
- 记忆化存储——涉及大规模重复计算的时候，可以考虑使用空间换时间的方法，通过记忆化存储的方式减少计算量。
官方题解
- 官解使用的是动态规划的方法，基础方法的逻辑基本上是一致的。
- 不过题解有个优化的方案将时间复杂度从O(n^3)优化到了O(n^2)，官解比较难懂所以参考了另外一个大佬的思路：
- 如果左区间小于右区间的一个子集，那么它必然小于包含该子集的任意右区间的区间情况，那么这个时候就不必再重复进行计算工作了，直接赋值最后结果即可——相当于在做剪枝。
- 所以可以直接计算所有n^2个的区间和，再通过大小比较和子集的包含情况来快速赋值，这样动态规划的过程中就不含O(L)的区间和计算了，只剩O(1)的加法运算。那么时间复杂度就可以降维成O(n^2)的预处理区间和计算和O(n^2)的动态规划，最后的时间复杂度就降维成O(n^2)了。官解的方法则是把预处理的逻辑插入了动态规划的计算中，通过剪枝的手段来实现优化，底层逻辑应该是差不多的。
)