刷题笔记0x08:石子游戏
题目描述
思路
首先,我们要求的答案是两人中谁会赢,或者说最终谁手中的石子数多。
其次,我们知道两人都是高手,将发挥出最高水平,并且石子总数为奇数,一定会有人赢。
那么让我们假设f(i, j)为对于一个序列索引i到j区间内,先手玩家最大所得与后手玩家最大所得的差值。
先假设个数组piles为[2, 7, 3, 9]的例子画个图看看。
先不急着把所有情况填满,显而易见的是,对于i == j的情况,差值显然就等于piles[i]或者说piles[j]了(因为这种情况区间里就一堆石头啊,后手根本没得拿)。
另外还可以发现,类似i == 1, j == 3和i == 3, j == 1的情况,它们表示的是同样的区间,所以我们可以抛弃表格左下角,并假定0 <= i <= size && i <= j <= size
,其中size表示题目给定的数组长度。
但是这样好像不太好总结规律,让我们稍微调整一下表格,每个表格里放两个数,分别表示先手可得的石子数和后手可得的石子数。
对于先手而言,只有两种选择,拿左边的或者右边的,我们设置一个三维数组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;
EOF