致虚极 守静笃
刷题笔记0x08:石子游戏
2020-04-21发布 279

题目描述

题目描述

思路

首先,我们要求的答案是两人中谁会赢,或者说最终谁手中的石子数多。

其次,我们知道两人都是高手,将发挥出最高水平,并且石子总数为奇数,一定会有人赢。

那么让我们假设f(i, j)为对于一个序列索引ij区间内,先手玩家最大所得与后手玩家最大所得的差值。

先假设个数组piles[2, 7, 3, 9]的例子画个图看看。

image

先不急着把所有情况填满,显而易见的是,对于i == j的情况,差值显然就等于piles[i]或者说piles[j]了(因为这种情况区间里就一堆石头啊,后手根本没得拿)。

另外还可以发现,类似i == 1, j == 3i == 3, j == 1的情况,它们表示的是同样的区间,所以我们可以抛弃表格左下角,并假定0 <= i <= size && i <= j <= size,其中size表示题目给定的数组长度。

image

但是这样好像不太好总结规律,让我们稍微调整一下表格,每个表格里放两个数,分别表示先手可得的石子数和后手可得的石子数。

image

对于先手而言,只有两种选择,拿左边的或者右边的,我们设置一个三维数组dp[i][j][2]dp[i][j][0]表示先手在区间内可得石子数,dp[i][j][1]就是后手的了。

dp[i][j][0] = max(piles[i] + dp[i-1][j][1], piles[j] + dp[i][j-1][1]);
/*
当我是先手时,比如说我拿走最右边一堆piles[j],
那么当前情况,相当于是对方是先手(dp[i][j-1][0])
而我变成dp[i][j-1]情况下的后手
拿左边同理
*/

// 先手拿了左边时,后手是[i-1][j]情况下的先手
dp[i][j][1] = dp[i-1][j][0];
// 同理先手拿走右边时
dp[i][j][1] = dp[i][j-1][0];

// 再回到我们最开始发现的规律
// if i == j: 先手拿走唯一的那堆石头
dp[i][j][0] = piles[i];
dp[i][j][1] = 0;

代码实现

具体写代码时,我们要得到的答案就是表格的右上角dp[i][j][0] > dp[i][j][1]这个表达式是否为true,也就是先手是不是比后手拿的石头多。为此,我们可以试着斜着遍历数组直到右上角。

bool stoneGame(int* piles, int pilesSize)
{
    int dp[pilesSize][pilesSize][2];
    memset(dp, 0, sizeof(dp));

    // 基准情况
    for (int i = 0; i < pilesSize; i++)
    {
        dp[i][i][0] = piles[i];
        dp[i][i][1] = 0;
    }

    // 斜着遍历数组
    for (int l = 2; l <= pilesSize; l++)
    {
        for (int i = 0; i <= pilesSize - l; i++)
        {
            int j = l + i - 1;
            int left = piles[i] + dp[i+1][j][1];
            int right = piles[j] + dp[i][j-1][1];
            // 省去写一个max函数
            if (left > right)
            {
                dp[i][j][0] = left;
                dp[i][j][1] = dp[i+1][j][0];
            }
            else
            {
                dp[i][j][0] = right;
                dp[i][j][1] = dp[i][j-1][0];
            }
        }
    }
    return dp[0][pilesSize-1][0] > dp[0][pilesSize-1][1];
}

后记

这道题的条件我隐约觉得有些不对劲,翻了一下评论,果然,这个游戏居然先手必胜,也就是说这题有个时间复杂度为O(1)的解法:

return true;

想不到吧