请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

Leetcode 877 石子游戏 这样的递归定义和实现对不对

------前言,要提的问题在下面------
这题我考虑先用记忆化搜索的方式解决,刚开始定义的递归函数定义得不好。
思路是这样的:先求出,在双方发挥最佳水平下,Alice 能取得石子的最大数量。用石子总数量减去这个最大数量得到的差,如果大于 0,说明 Alice 能赢得比赛。
这样定义出来的递归函数,参数不仅要有剩余石头的 「左边界」和「右边界」,还要有「剩余石子的数量」,要记忆的空间特别大。用 Map 来记忆化,一提交,耗时 1964 ms,勉强通过。后来再次尝试提交,超时。

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int sum = accumulate(piles.cbegin(), piles.cend(), 0);
        int a = alice(piles, 0, piles.size() - 1, sum);
        return a > sum - a;
    }

private:
    map<vector<int>, int> a;
    map<vector<int>, int> b;

    // alice 从 piles[lo...hi] 中取石头所能得到的最大总数,双方都发挥出最佳水平
    int alice(const vector<int> &piles, int lo, int hi, int sum) {
        if (lo > hi) {
            return 0;
        }

        if (a.find({ lo, hi, sum }) != a.cend()) {
            return a[{ lo, hi, sum }];
        }

        return a[{ lo, hi, sum }] = max(sum - bob(piles, lo + 1, hi, sum - piles[lo]),
                                        sum - bob(piles, lo, hi - 1, sum - piles[hi]));
    }

    // bob 从 piles[lo...hi] 中取石头所能得到的最大总数,双方都发挥出最佳水平
    int bob(const vector<int> &piles, int lo, int hi, int sum) {
        if (lo > hi) {
            return 0;
        }

        if (b.find({ lo, hi, sum }) != b.cend()) {
            return b[{ lo, hi, sum }];
        }

        return b[{ lo, hi, sum }] = max(sum - alice(piles, lo + 1, hi, sum - piles[lo]),
                                        sum - alice(piles, lo, hi - 1, sum - piles[hi]));
    }
};

于是,我绞尽脑汁,想着怎样定义一个好的递归函数,才不用记忆像「剩余石子的数量」这种这么大范围的参数。
没思路,于是就参考了老师代码仓库中的代码,主要看了 main.cpp
研究了几十分钟,还是不太明白函数的定义,主要没搞懂函数 play() 实现里的加法、减法是怎么得来的。
但此时有了自己的想法,我就试着按照自己的思路写了下:

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        memo = vector<vector<vector<int>>>(2, vector<vector<int>>(n, vector<int>(n, INT_MIN)));
        return play(piles, 0, piles.size() - 1, 0) > 0;
    }

private:
    vector<vector<vector<int>>> memo;

    // 从剩下的 piles[lo...hi] 中取石子,当前选手与另一个选手的石子数量之差的最大值,每位选手都发挥出最佳水平
    int play(const vector<int> &piles, int lo, int hi, int player) {
        if (lo == hi) {
            return piles[lo];
        }

        if (memo[player][lo][hi] != INT_MIN) {
            return memo[player][lo][hi];
        }

        return memo[player][lo][hi]= max(-play(piles, lo + 1, hi, 1 - player) + piles[lo],
                                         -play(piles, lo, hi - 1, 1 - player) + piles[hi]);
    }
};

问题:

  1. 这样一提交,代码运行耗时 40 ms。虽然通过了,但不知道自己的思路和实现对不对,毕竟这题的题解可以直接 return true 通过。
  2. 不知我的解法跟 main.cpp 有啥不同, 就试着拿题目中「示例 1」的测试用例 piles = [5,3,4,5] 和「示例 2」 piles = [3,7,2,3] 来调用 play() 函数。对于「示例 1」的测试用例,我的输出 1, main.cpp 的输出 3。对于「示例 2」的测试用例,都输出 5。对于「示例 1」的测试用例调用 play() 的输出结果不一样,我动笔验证了下,输出 1 确实符合我的函数定义,毕竟题目要求双方都发挥出最佳水平,如果输出 3,虽然 Alice 获胜了,但显然 Bob 放水了。 于是,我想我可能不清楚 main.cpp 中 play() 函数的定义是什么,或许我的代码思路有问题了。

正在回答 回答被采纳积分+3

插入代码

1回答

liuyubobobo 2022-08-14 16:00:52

你的实现是正确的。实际上,你的代码比我的 main.cpp 的思路简单:)


在你的代码下, player 这一维度的状态是没有用的。可以参考我精简后的 main5.cpp:https://github.com/liuyubobobo/Play-Leetcode/blob/master/0501-1000/0877-Stone-Game/cpp-0877/main5.cpp


2

这个方法和我的 main.cpp 定义的状态不同。之所以定义的状态不同,原因就在于是否有 player 这个状态。


简单来说,我的 main.cpp 的状态定义,固定在了 player == 0 的视角下。也就是:play(player, l, r) 的意思是:当前由 player 行动,剩余的石子是 [l, r] 的范围时,player0 的最大得分。

所以,下面的逻辑中,会有一个 if,如果当前的 player 就是 player0 的话,他拿的石子算作正分;否则(player1),是负分(相对于 player0 是负的);


你的方法则没有固定 play == 0 的视角,play(l, r) 就是当前的玩家在面对 [l, r] 的式子的时候的最佳得分。所以,这个最佳得分,直接是拿走一堆石子的分数(正数)减去下一个玩家面对剩下的石子的得分。


继续加油!:) 

0 回复 有任何疑惑可以回复我~
  • 提问者 慕村510262 #1
    1. 好神奇,这样简化都行,一时脑筋转不过来,不太明白。
    2. 对于「示例 1」的测试用例 piles = [5,3,4,5] 调用 main.cpp 的 play 函数,输出 3,好像有点不太对,没有考虑到题目中「假设 Alice 和 Bob 都发挥出最佳水平」。Bob 如果发挥最佳水平的话,Bob 能拿 5+3 个石子,Alice 只能拿 5+4 个石子,也即俩人数量差为 1。
    回复 有任何疑惑可以回复我~ 2022-08-14 17:35:28
  • liuyubobobo 回复 提问者 慕村510262 #2
    你是正确的,我原先的代码是错误的。我的代码当固定 player == 0 的视角以后,在 player = 1 的时候,选择的也是最大化 player = 0 的行动,但这是不符合题意的,应该选择最大化 player = 1 的行动。
    
    这个思路的修改代码现在在这里:https://github.com/liuyubobobo/Play-Leetcode/blob/master/0501-1000/0877-Stone-Game/cpp-0877/main2.cpp
    
    注意:45 行变成了 min。也就是当 player == 1 的时候,因为此时的分数在 player == 0 的视角变成了负的,所以 play1 要最小化这个负的得分(也就是最大化 player1 自己的得分。)
    
    大赞!抱歉!
    回复 有任何疑惑可以回复我~ 2022-08-15 01:34:24
  • 提问者 慕村510262 回复 liuyubobobo #3
    懂了,谢谢老师的回答!
    回复 有任何疑惑可以回复我~ 2022-08-15 19:58:22
问题已解决,确定采纳
还有疑问,暂不采纳
意见反馈 帮助中心 APP下载
官方微信