1563. 石子游戏 V - 力扣LeetCode题目几块石子排成一行每块石子都有一个关联值关联值为整数由数组stoneValue给出。游戏中的每一轮Alice 会将这行石子分成两个非空行即左侧行和右侧行Bob 负责计算每一行的值即此行中所有石子的值的总和。Bob 会丢弃值最大的行Alice 的得分为剩下那行的值每轮累加。如果两行的值相等Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。只剩下一块石子时游戏结束。Alice 的分数最初为0。返回Alice 能够获得的最大分数。示例 1输入stoneValue [6,2,3,4,5,5]输出18解释在第一轮中Alice 将行划分为 [623][455] 。左行的值是 11 右行的值是 14 。Bob 丢弃了右行Alice 的分数现在是 11 。 在第二轮中Alice 将行分成 [6][23] 。这一次 Bob 扔掉了左行Alice 的分数变成了 1611 5。 最后一轮 Alice 只能将行分成 [2][3] 。Bob 扔掉右行Alice 的分数现在是 1816 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(vectorint stoneValue, int start, int end) { int sum 0; for(int i start; i end; i) sum stoneValue[i]; return sum; } int getMaxScore(vectorint 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, i1, end); currentScore min(leftSum, rightSum); if(leftSum rightSum) maxScore max(maxScore, currentScoregetMaxScore(stoneValue, start, i)); else if(leftSum rightSum) maxScore max(maxScore, currentScoregetMaxScore(stoneValue, i1, end)); else { maxScore max(maxScore, currentScoregetMaxScore(stoneValue, start, i)); maxScore max(maxScore, currentScoregetMaxScore(stoneValue, i1, end)); } } return maxScore; } int stoneGameV(vectorint stoneValue) { return getMaxScore(stoneValue, 0, stoneValue.size()-1); } };显然这样的方法随着递归层数的增加效果是非常差的最差估计能接近O(2^n)。可以注意到递归的过程中发生了多次的重复计算根据智能分析的建议和较优复杂度情况可以采用记忆化存储的方式设置n*n的状态数组vv[i][j]表示从i到j这个区间的最大得分调用的过程中先查查这个得分是否被计算了若已经被计算就直接赋值即可。class Solution { public: int countSum(vectorint stoneValue, int start, int end) { int sum 0; for(int i start; i end; i) sum stoneValue[i]; return sum; } int getMaxScore(vectorvectorint partialValue,vectorint 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, i1, end); currentScore min(leftSum, rightSum); if(leftSum rightSum) { if(partialValue[start][i] -1) partialValue[start][i] getMaxScore(partialValue, stoneValue, start, i); maxScore max(maxScore, currentScorepartialValue[start][i]); } else if(leftSum rightSum) { if(partialValue[i1][end] -1) partialValue[i1][end] getMaxScore(partialValue, stoneValue, i1, end); maxScore max(maxScore, currentScorepartialValue[i1][end]); } else { if(partialValue[start][i] -1) partialValue[start][i] getMaxScore(partialValue, stoneValue, start, i); maxScore max(maxScore, currentScorepartialValue[start][i]); if(partialValue[i1][end] -1) partialValue[i1][end] getMaxScore(partialValue, stoneValue, i1, end); maxScore max(maxScore, currentScorepartialValue[i1][end]); } } return maxScore; } int stoneGameV(vectorint stoneValue) { int len stoneValue.size(); vectorvectorint partialValue(len, vectorint(len, -1)); return getMaxScore(partialValue, stoneValue, 0, len-1); } };结果还是超时了最后分析之后发现countSum行为才是大量重复计算的根源直接改成前缀和计算能节省大量的时间开销。代码实现class Solution { public: int countSum(vectorint stoneValue, int start, int end) { int sum 0; for(int i start; i end; i) sum stoneValue[i]; return sum; } int getMaxScore(vectorvectorint partialValue,vectorint 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, currentScorepartialValue[start][i]); } else if(leftSum rightSum) { if(partialValue[i1][end] -1) partialValue[i1][end] getMaxScore(partialValue, stoneValue, i1, end); maxScore max(maxScore, currentScorepartialValue[i1][end]); } else { if(partialValue[start][i] -1) partialValue[start][i] getMaxScore(partialValue, stoneValue, start, i); maxScore max(maxScore, currentScorepartialValue[start][i]); if(partialValue[i1][end] -1) partialValue[i1][end] getMaxScore(partialValue, stoneValue, i1, end); maxScore max(maxScore, currentScorepartialValue[i1][end]); } } return maxScore; } int stoneGameV(vectorint stoneValue) { int len stoneValue.size(); vectorvectorint partialValue(len, vectorint(len, -1)); return getMaxScore(partialValue, stoneValue, 0, len-1); } };复杂度分析时间复杂度因为会考虑所有区间区间总数为n(n1)/2O(n^2)再加上每个区间会进行一次比那里长度为O(L)不妨近似为O(n)——所以总的时间复杂度应该是O(n^3)。空间复杂度O(n^2)——引入了记忆化存储的n*n的数组其余开销为栈开销最坏是O(n)。知识积累vector初始化(以二层为例)vectorvectorint 变量名(外层长度, vectorint(内层长度, 初始值));vector初始化的另一种形式变量名.assign(外层长度, vectorint(内层长度))——估计默认值为0.记忆化存储——涉及大规模重复计算的时候可以考虑使用空间换时间的方法通过记忆化存储的方式减少计算量。官方题解官解使用的是动态规划的方法基础方法的逻辑基本上是一致的。不过题解有个优化的方案将时间复杂度从O(n^3)优化到了O(n^2)官解比较难懂所以参考了另外一个大佬的思路如果左区间小于右区间的一个子集那么它必然小于包含该子集的任意右区间的区间情况那么这个时候就不必再重复进行计算工作了直接赋值最后结果即可——相当于在做剪枝。所以可以直接计算所有n^2个的区间和再通过大小比较和子集的包含情况来快速赋值这样动态规划的过程中就不含O(L)的区间和计算了只剩O(1)的加法运算。那么时间复杂度就可以降维成O(n^2)的预处理区间和计算和O(n^2)的动态规划最后的时间复杂度就降维成O(n^2)了。官解的方法则是把预处理的逻辑插入了动态规划的计算中通过剪枝的手段来实现优化底层逻辑应该是差不多的。