X

LEETCODE 1563. Stone Game V 解题思路分析

题目大意:

石子游戏 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 <= 500
  • 1 <= 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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1563-stone-game-v-解题思路分析/
Categories: leetcode
kwantong: