LEETCODE 1406. Stone Game III 解题思路分析

题目大意:

石子游戏 III

Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行,每堆石子都对应一个得分,由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子,Alice 总是先开始。在每个玩家的回合中,该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分,得分最高的选手将会赢得比赛,比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 “Alice” ,Bob 赢了就返回 “Bob”,平局(分数相同)返回 “Tie” 。

示例 1:

输入:values = [1,2,3,7]
输出:"Bob"
解释:Alice 总是会输,她的最佳选择是拿走前三堆,得分变成 6 。但是 Bob 的得分为 7,Bob 获胜。

示例 2:

输入:values = [1,2,3,-9]
输出:"Alice"
解释:Alice 要想获胜就必须在第一个回合拿走前三堆石子,给 Bob 留下负分。
 如果 Alice 只拿走第一堆,那么她的得分为 1,接下来 Bob 拿走第二、三堆,得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆,输掉比赛。
 如果 Alice 拿走前两堆,那么她的得分为 3,接下来 Bob 拿走第三堆,得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆,同样会输掉比赛。
 注意,他们都应该采取 最优策略 ,所以在这里 Alice 将选择能够使她获胜的方案。

示例 3:

输入:values = [1,2,3,6]
输出:"Tie"
解释:Alice 无法赢得比赛。如果她决定选择前三堆,她可以以平局结束比赛,否则她就会输。

示例 4:

输入:values = [1,2,3,-1,-2,-3,7]
输出:"Alice"

示例 5:

输入:values = [-1,-2,-3]
输出:"Tie"

提示:

  • 1 <= values.length <= 50000
  • -1000 <= values[i] <= 1000

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1406

解题思路分析:

遇到这种有n种选择然后找最优解的问题,我们应该下意识想到使用动态规划DP来解题。我们在之前的文章多次讲过,动态规划实际上也是带记忆的递归。本文我们会分别给出这两种解法的代码。

首先,本题是一道游戏题目,游戏中有2个玩家。对于这种题,我们是不需要模拟出2个人物去解题的。实际上2个人的逻辑没有任何差别,对于任意一个人,当前都有3种选择(小于3堆时的选择会小于3种),选择拿1堆,2堆或者3堆。做出哪种选择取决于哪种选法能够使自身利益最大化。

解题时我们先建立一个递归函数,参数是当前index,以及当前剩下的石头的总分数sum。返回结果为当前index到数组末尾,当前玩家可以拿到最多的石头分数。由于此时我们无法判断出哪一种选择最优,因此我们必须对3种选择分别进行尝试(选择综合征的福音)。当选择第一堆石头后,当前index增加1,当前石头总量sum减少了第一堆石头的得分。我们将该情况递归到子问题中去求解。同理,我们选择前两堆石头后,index增加2,石头总量sum减少了前两堆石头的得分。选择前三堆石头也同理。

三个递归函数能够返回3种结果,这3种结果也是对手在当前用户做出每一种选择后给出的相应最优解。那么当前玩家该做出哪一种选择呢?显然让自身利益最大化,一定让对手利益最小化,因此三个结果中最小的一方应该是选择的对象,我们使用当前sum减去三种递归函数中最小的返回结果,就是当前递归函数的返回值。递归函数的终止条件是当前index是数组的最后一位时,当前用户别无选择,只能选择剩下的这一堆。

实现代码:

Integer[] memo; // 记忆数组
public String stoneGameIII(int[] stoneValue) {
    memo=new Integer[stoneValue.length]; // 初始化记忆数组
    int sum=0; // 计算所有石头的分数和
    for(int val : stoneValue) sum+=val;
    // 递归求出alice能够拿到的最多分数。
    int aliceScroe=help(stoneValue,0,sum);
    // 总分数减去alice的分数即是bob的分数
    int bobScroe=sum-aliceScroe;
    // 利用2人分数判断获胜方
    if(aliceScroe>bobScroe) return "Alice";
    else if(aliceScroe<bobScroe) return "Bob";
    else return "Tie";
}
// stoneValue:石头数组
// index:当前下标
// sum:当前下标到数组结尾处所有石头的分数和
// 返回值:在当前下标后所有石头中,当前玩家能拿到的最大分数
int help(int[] stoneValue,int index,int sum){
    // 如果下标越界,返回0
    if(index==stoneValue.length) return 0;
    // 如果下标是最后一位,别无选择,返回最后一个石头分数
    if(index==stoneValue.length-1) return stoneValue[index];
    // 如果记忆数组存在当前解,返回记忆数组中的值
    if(memo[index]!=null) return memo[index];
    int tempSum=sum;
    // 循环3种选择(拿前1,2,3堆石头)
    int min=Integer.MAX_VALUE;
    for(int i=index;i<stoneValue.length&&i-index<3;i++){
        // 总分数减去当前拿掉的分数
        tempSum-=stoneValue[i];
        // 递归求解找到一个最小值
        min=Math.min(min,help(stoneValue,i+1,tempSum));
    }
    // 当前sum减去递归最小值为当前返回结果,存入记忆数组
    memo[index]=sum-min;
    return memo[index];
}

本题解法执行时间为73ms。

Runtime: 73 ms, faster than 36.99% of Java online submissions for Stone Game III.

Memory Usage: 134 MB, less than 100.00% of Java online submissions for Stone Game III.


接下来我们看一下DP动态规划的解法。其实动态规划与递归思想没有任何差别。我们定义一个dp数组,dp[i]代表,第i位到数组结尾间能拿到的最大分数,如果想拿到最大分数,那么一定要让对手拿到最少分数,因此:

dp[i] = sum[i, length-1]-min(dp[i+1],dp[i+2],dp[i+2])

实现代码:

ic String stoneGameIII(int[] stoneValue) {
    int[] dp=new int[stoneValue.length+1];
    dp[stoneValue.length-1]=stoneValue[stoneValue.length-1];
    int sum=stoneValue[stoneValue.length-1];
    for(int i=stoneValue.length-2;i>=0;i--){
        sum+=stoneValue[i];
        int min=Integer.MAX_VALUE;
        for(int j=i+1;j<=i+3&&j<=stoneValue.length;j++){
            min=Math.min(min,dp[j]);
        }
        dp[i]=sum-min;
    }
    if(dp[0]>sum-dp[0]) return "Alice";
    else if(dp[0]<sum-dp[0]) return "Bob";
    else return "Tie";
}

本题解法执行时间为6ms。

Runtime: 6 ms, faster than 97.82% of Java online submissions for Stone Game III.

Memory Usage: 48.6 MB, less than 100.00% of Java online submissions for Stone Game III.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1406-stone-game-iii-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。