题目大意：
石子游戏 V
几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 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] <= 10^6
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1563
解题思路分析：
爱丽丝和鲍勃又回来了！从题目的数据量就可以看出，本题目依旧是一个动态规划思路。游戏开始时，对于如何选择我们无法一眼看出答案，因此我们需要分别去尝试每一种选择，最后比较出最优方案。这正是动态规划的核心思想。对于动态规划题目，我习惯使用递归加记忆数组方式来解题，本题也不例外。
首先建立一个递归函数：
help(int[] stoneValue, int left, int right, int sum)
函数的返回值表示在区间left到right做游戏时，爱丽丝能获得的最大分数。函数参数中的sum参数为该区间内石子的值的总和。递归中，我们循环每一种切割方式，从下标0开始向后切割，另外利用一个变量leftSum记录切割后左边（left到当前下标）的数值和。而右区间和rightSum很显然是：sum-leftSum。我们将数值和较小一方递归至子问题求解，递归函数的解加上当前较小的数值和即是当前分割后，爱丽丝在当前区间left到right能得到的最高得分。但是该最高得分并不一定是当前区间的最高得分，我们需要遍历完每一种分割后才能得出最优解。因此循环中使用当前得分更新递归中的最大得分即可。最后本层递归返回该最大得分。
接下来再考虑记忆数组，本题递归函数中只存在2个实际变量，即区间的左右范围，因此我们使用一个二维数组memo[][]来记录递归函数的返回值即可。
实现代码：
int[][] memo; // 记忆数组
public int stoneGameV(int[] stoneValue) {
memo=new int[stoneValue.length][stoneValue.length]; // 初始化记忆数组
int sum=0; // 求和
for(int stone : stoneValue){
sum+=stone;
}
return help(stoneValue,0,stoneValue.length-1, sum); // 递归求最优解
}
// 返回值为：下标left到right区间内，爱丽丝能拿到的最大得分
// sum为当前区间内和
int help(int[] stoneValue, int left, int right, int sum){
// 如果记忆数组中存在该区间答案，直接返回
if(memo[left][right]>0) return memo[left][right];
int leftSum=0; // 左半边和
int max=0; // 最大值
for(int i=left;i<right;i++){ // 循环每一种分割
leftSum+=stoneValue[i]; // 累加左半边和
int rightSum=sum-leftSum; // 计算右半边和
if(leftSum>rightSum){ // 如果左边大于右边
int res=help(stoneValue, i+1, right, rightSum); // 使用右边继续游戏
max=Math.max(max, rightSum+res); // 当前分割后爱丽丝的分数，更新最大值
}else if(leftSum<rightSum){ // 如果左边小于右边
int res=help(stoneValue, left, i, leftSum); // 使用左边继续游戏
max=Math.max(max, leftSum+res); // 当前分割后爱丽丝的分数，更新最大值
}else{ // 如果左边等于右边
// 分别尝试使用两边继续游戏，寻找最优解
int resR=help(stoneValue, i+1, right, rightSum);
max=Math.max(max, rightSum+resR);
int resL=help(stoneValue, left, i, leftSum);
max=Math.max(max, leftSum+resL);
}
}
memo[left][right]=max; // 将最优解计入记忆数组
return max;
}本题解法执行时间为79ms。
Runtime: 79 ms, faster than 56.25% of Java online submissions for Stone Game V.
Memory Usage: 49.1 MB, less than 6.25% of Java online submissions for Stone Game V.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1563-stone-game-v-解题思路分析/