前言
大家好，今天我们来聊聊动态规划的第二大类问题——石子问题。
我们上一篇文章讲解了Top Down 这种 DP 解法，本文主要讲解 Bottom Up这两种 DP 解法。
那在看题目之前，我们稍微来回顾一下动态规划和博弈。
解题思路二、Bottom Up
正如我们前文所说，与 Top Down 不同的是，我们会先 initialize Base Case，然后通过 Base Case 一层一层的根据关系式往上面建立。
在这里我们的 Base Case 是 l==r 的时候，l==r 就是只剩下一个石子的时候，如果这个回合是小六，他能得到所有的分数，如果是小七，她得到的是0分（因为 play 函数是指小六的分数而不是小七的）。
DP 关系转移:
- 小六： 我们用
dp[l][r][0]去表示当前是小六的回合，他能拿的数组[l:r]的数
- 如果小六拿第一个，区间会变成
[l+1:r]，下一个player是1，那就是A[l]+dp[l+1][r][1] - 如果小六拿最后一个，区间会变成
[l:r-1]，下一个player是1，那就是A[r]+dp[l][r-1][1] - 小六要取最大的那一个，综上，关系式就是
dp[l][r][0]=Math.max(A[l]+dp[l+1][r][1],A[r]+dp[l][r-1][1])
- 小七：我们用
dp[l][r][1]去表示当前是小七的回合，她能拿的数组[l:r]的数。(小七的分数不计入play函数里面)
- 如果小七拿第一个，区间会变成
[l+1:r]，下一个player是0，那就是dp[l+1][r][0] - 如果小七拿最后一个，区间会变成
[l:r-1]，下一个player是0，那就是dp[l][r-1][0] - 小七要取最小的那一个，综上，关系式就是
dp[l][r][1]=Math.min(dp[l+1][r][0],dp[l][r-1][0])
下一步：
- 我们需要注意的只剩下
dp填表的顺序。我们需要保证求当前的状态时，之前的状态已经是记录好了的 - 我们会按
(0,0),(1,1),(2,2) ... (n,n), (0,1),(1,2),(2,3) ... (0,2),(1,3),(2,4)...这样的顺序打表
完整代码 Bottom Up
classSolution {
publicbooleanstoneGame(int[] A) {
intdp[][][] =newint[A.length][A.length][2];
intsum=0;
for (inti=0; i<A.length; i++) {
sum+=A[i];
}
for (inti=0; i<dp.length; i++) {
dp[i][i][0] =A[i];
dp[i][i][0] =0; // 对 base 的初始化
}
for (inti=1; i<dp.length; i++) {
for (intl=0; l+i<dp.length; l++) {
dp[l][l+i][0] =Math.max(A[l] +dp[l+1][l+i][1], A[l+i] +dp[l][l+i-1][1]);
dp[l][l+i][1] =Math.min(dp[l+1][l+i][0], dp[l][l+i-1][0]);
}
}
//dp[0][A.length-1][0] 代表小六能从数组区间[0,len(A)-1]能拿到的最大分数
returndp[0][A.length-1][0] *2>sum;
}
}
代码总结：
- 对于
Bottom UP我们先对 Base Cass 进行初始化，这里的 Base Case 是l==r的时候 - 这里的关系式我们可以从
Top Down那里看的出来，做 DP 的时候建议先Top Down再Bottom UP会比较容易 - 需要注意打表的顺序，保证求当前的状态时，之前的状态已经是记录好了的.
- 时间和空间复杂度跟
Top Down是一样的
时空复杂度分析
同样都是 O(N^2)。
- 空间复杂度：O(N^2)
- 时间复杂度：O(N^2)
学会了石子游戏 I 之后，让我们来乘胜追击，一起来攻破一下难度是 HARD 的石子游戏 III～
（为了方便 C++ 读者，本题使用 C++ 进行实现）
Stone Game III
题意：
给你一组数组
A=[1,2,3,7]，同样还是小六(先手)和小七轮流从里面取数字，但 ，两人这次只能从左边拿数字，一次可以拿 1~3 个，取完之后这数字会从A中移除，问谁是最后的赢家如果两个人每次都采取对自己最有利的方案。分数最多者为胜利者。
解题思路一、Top Down
对于每个 player 来说，他都有三种选择（以第一轮为例）：
- 如果小六选了
A[0], 那么他会留下[2,3,7]给小七做选择； - 如果他选的是
A[0]+A[1], 他会留下[3,7]给小七做选择； - 如果他选的是
A[0]+A[1]+A[2], 他会留下[7]给小七做选择；
从例子来看，无论小六怎么拿，小七都能获胜，因为她能拿到最后一个 7。
如果我们选择暴力的话，我们可以把所有的可能性都列举出来。
当某一个 player 选掉一个数字后，他可以把剩下的数字递归给下一位 player，当所有数字取完时，游戏结束。
这里我们可以得到一个观察，因为数字只能从左边取，我们可以用一个区间 [l,r] 去表达剩下的数字。
如果我们取第一个，新的 A 会变成 [l+1,r] ；如果我们取前两个，新的 A 是 [l+2,r]。并且因为 r 是固定的，我们可以把其省略。
与 Stone Game I 同理，我们还需要一个额外的 player variable 去记录当前是谁的回合 (不同的 player 会用不同的决策)。
play函数的返回值是小六能拿的分数。如果最终这个分数在总分数一半以上的话，小六能获胜，反之，小七获胜或平手。- 身为小六，如果他想要拿到最多的分，选择最大的那一个。
- 身为小七，同样有三个选择。
但跟小六不一样的是，小七会选择返回一个最小的数给小六因为她不想让小六获胜。 - 最终我们的代码将能用
dp[l][player]去表达我们的压缩状态，[l]就如之前所说，表示当前剩下的数字的范围，player 代表当前是谁的回合。 - 我们用
0代表小六，1代表小七 。
完整代码 Top Down
classSolution {
public:
stringstoneGameIII(vector<int>&A) {
vector<vector<int>>dp(A.size(), vector<int>(2, INT_MIN));
intsum=0;
for (intx : A) {
sum+=x;
}
intmaxScore=dfs(dp, A, 0, 0); // 小六能拿到最大的分数
// 根据分数有三种情况
if (maxScore*2>sum) {
return"Alice";
} elseif (maxScore*2<sum) {
return"Bob";
} else {
return"Tie";
}
}
intdfs(vector<vector<int>>&dp, vector<int>&A, intl, intplayer) {
if (l>=A.size()) { // 所有数被取完的情况
return0;
}
if (dp[l][player] !=INT_MIN) { // 如果是已经访问过的状态，我们不需要再重新计算
returndp[l][player];
}
intnextPlayer= (player+1) %2;
intres=INT_MIN;
if (player==0) {
intscore=0;
for (inti=1; i<=3; i++) {
if (l+i-1<A.size()) {
score+=A[l+i-1]; // 注意有可能剩下不够3个的情况，防止 outbound
}
res=max(res, score+dfs(dp, A, l+i, nextPlayer));
}
}
else {
res=INT_MAX; // 我们要取最小的关系，所以把res设成INT_MAX
for (inti=1; i<=3; i++) { //这里不用在意outbound，outbound情况下递归直接返回0
res=min(res, dfs(dp, A, l+i, nextPlayer));
}
}
dp[l][player] =res;// 对状态的值的储存
returnres;
}
};
代码总结 ：
- 同 Stone Game I一样，
play函数就是我们的主要逻辑所在，play函数值是小六能得到的最大分数。 - 我们用
[l,r]去表示还剩下哪些数字，player去表示当前的回合。nextPlayer是下一个回合。如果当前回合是0，下一个回合就是1。如果当前回合是1，下一个回合就是0。我们用nextPlayer = (player + 1) % 2但因为r是固定的，我们可以单纯用l来表示就够了。 - 我们有三种情况，
player是0和是1的情况。如果是0(先手小六)，他想得到的是最大的分数，所以我们传回一个max。如果是1（小七后手），她想要小六拿到最小，所以我们回传一个最小。 注意，小七的回合我们不用加上A[l]或者A[r]，因为play是小六的分数，所以小七回合的A[l]或者A[r]不用归入小六里面。
时空复杂度：
空间复杂度就非常明显是 2 * O(N) 。
时间复杂度是play函数的状态个数乘每个play函数的时间复杂度。
我们一共有 2N 的状态，play函数的空间是 O(3)，所以时间复杂度也是 3 * O(2N)。 简化一下就是 O(N)。
- 空间复杂度：O(N)
- 时间复杂度：O(N)
解题思路二、Bottom Up
思路：
同理，我们要先对 Base Case 进行 initialize。
这里的Base Case 是都取完outbound的时候，所以可以不用进行特别的初始化。
DP 关系转移：
- 小六：我们用
dp[l][0]去表示当前是 小六的回合，他能拿的数组[l:A.size()-1]的数
- 如果小六拿第一个，区间会变成
[l+1],下一个player是1，那就是A[l]+dp[l+1][1] - 如果小六拿第前两个，区间会变成
[l+2],下一个player是1，那就是A[l]+A[l+1]+dp[l+2][1] - 如果小六拿第前三个，区间会变成
[l+3],下一个player是1，那就是A[l]+A[l+1]+A[l+2]+dp[l+3][1] - 综上，关系式就是
dp[l][0]=max(A[l]+dp[l+1][1],A[l]+A[l+1]+dp[l+2][1],A[l]+A[l+1]+A[l+2]+dp[l+3][1])可能会有 outbound 的情况，我们可以用 if statement 做特殊处理
- 小七：我们用
dp[l][1]去表示当前是 小七的回合，她能拿的数组[l:A.size()-1]的数。(小七的分数不计入play函数里面)
- 如果小七拿第一个，区间会变成
[l+1],下一个player是1，那就是A[l]+dp[l+1][1] - 如果小七拿第前两个，区间会变成
[l+2],下一个player是1，那就是A[l]+A[l+1]+dp[l+2][1] - 如果小七拿第前三个，区间会变成
[l+3],下一个player是1，那就是A[l]+A[l+1]+A[l+2]+dp[l+3][1] - 综上，关系式就是
dp[l][1]=min(dp[l+1][0],dp[l+2][0],dp[l+3][0])可能会有 outbound 的情况，这种情况dp[outbound][0]=0
下一步：
- 我们需要注意的只剩下 dp 填表的顺序。我们需要保证求当前的状态时，之前的状态已经是记录好了的
- 从关系式
dp[l][0]=max(A[l]+dp[l+1][1],A[l]+A[l+1]+dp[l+2][1],A[l]+A[l+1]+A[l+2]+dp[l+3][1])和dp[l][0]=min(dp[l+1][1],dp[l+2][0],dp[l+3][0])和 我们这里可以直接按直线的顺序来打表，从n开始到0进行打表
完整代码 Bottom Up
classSolution {
public:
stringstoneGameIII(vector<int>&A) {
vector<vector<int>>dp(A.size(), vector<int>(2, INT_MIN));
intsum=0;
for (intx : A) {
sum+=x;
}
for (intl=A.size() -1; l>=0; l--) {
intmn=INT_MAX;
intmx=INT_MIN;
intscore=0;
for (intj=0; j<3; j++) { // player0 的三种选择
if (l+j<A.size()) { // 注意outbound
score+=A[l+j];
}
if (l+j+1<A.size()) {
mx=max(mx, score+dp[l+j+1][1]);
} else {
mx=max(mx, score);
}
}
for (intj=0; j<3; j++) { // player0 的三种选择
if (l+j+1<A.size()) {
mn=min(mn, dp[l+j+1][0]);
} else {
mn=min(mn, 0);
}
}
dp[l][0] =mx;
dp[l][1] =mn;
}
intmaxScore=dp[0][0];
//三种情况
if (maxScore*2>sum) {
return"Alice";
} elseif (maxScore*2<sum) {
return"Bob";
} else {
return"Tie";
}
}
};
代码总结：
- 和 Stone Game 一样非常类似，如果我们一开始不知道怎么推理关系式，我们可以先从
Top Down或者暴力开始。 - 知道关系之后我们就可以打表了，先初始化 Base Case， 然后只要保证求当前的状态时，之前的状态已经是记录好了的就没问题。
空间复杂度和时间复杂度：
- 空间复杂度：O(N)
- 时间复杂度：O(N)
总结
LeetCode 的 Stone Game 系列有 7 题之多，但大多数的套路都是类似的，相信大家通过这两道题已经有些思路，对博弈和 DP 有一个更好的理解。
- 对于 DP，它是一种状态的表达和压缩。
由石子游戏我们可以看见，从暴力出发我们是把数字从数组里移除掉再把这个新的数组递给下一个回合。
但是因为其移取的规律性，我们可以用区间[l:r] 来进行对数组状态的表达，从而可以做到像斐波那契那样进行cache 和记忆化。
DP题目我们一般都可以从暴力或者 Top Down 出发，找出关系后可进行优化成 Bottom Up 的模式。
- 对于博弈，它是一门比较博大精深的东西。
这里我们涉及到的只是比较基本的层面，加上Stone Game 取石子是有规律性的所以我们可以做到一个压缩达到优化。
也有一些游戏系列是有必胜策略的，（听说五子棋先手必胜）这种题目我们可以用贪心来解，之后再分享这一类的问题～
