假设有两个人爱丽丝和鲍勃，他们正在用石头堆继续比赛。一排有许多堆，每堆中有正整数的石头排成一堆[i]。我们游戏的目标是以最多的石头作为结局。爱丽丝(Alice)和鲍勃(Bob)转弯，爱丽丝(Alice)首先出发。最初，M =1。在每个玩家的回合中，该玩家可以拿走剩下的前X堆中的所有石头，这里1 <= X <= 2M。然后，我们设置M = max(M,X)。没有结石时，游戏结束。因此，如果桩= [2,7,9,4,4]，则输出将为10。这是因为，如果爱丽丝在开始时拿了一个桩，那么鲍勃拿了两个桩，然后爱丽丝又拿了2个桩。爱丽丝手上可以拿到2 + 4 + 4 = 10堆。如果爱丽丝一开始拿了两堆，那么鲍勃可以拿走剩下的三堆。在这种情况下，爱丽丝得到2 + 7 = 9堆。因为它更大，所以我们将获得收益10。
为了解决这个问题，我们将遵循以下步骤-
创建一个称为Solve的递归函数，它将使用数组i，m和一个称为dp的矩阵。
如果i> = arr的大小，则返回0
如果dp [i，m]不为-1，则返回dp [i，m]
如果i – 1 + 2m> =数组大小，则返回arr [i]
op：= inf
适用于1到2m范围内的x
op：= op的最小值，solve（arr，i + x，x和m的最大值，dp）
dp [i，m]：= arr [i] – op
返回dp [i，m]
实际的方法将是-
n：=堆数组的大小，使一个数组称为大小n的arr
arr [n-1]：=桩[n – 1]
对于i：= n – 2降至0
arr [i]：= arr [i + 1] +桩[i]
创建一个大小为（n + 1）x（n + 1）的矩阵，并用-1填充
返回solve(arr,0,1,dp)
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void printVector(vector <int> v){
for(int i =0;i<v.size();i++)cout << v[i] << " ";
cout << endl;
}
int stoneGameII(vector<int>& piles) {
int n = piles.size();
vector <int> arr(n);
arr[n-1] = piles[n-1];
for(int i = n-2;i>=0;i--)arr[i] = arr[i+1] + piles[i];
vector < vector <int> > dp(n+1,vector <int> (n+1,-1));
return solve(arr,0,1,dp);
}
int solve(vector <int> arr, int i, int m, vector < vector <int> > &dp){
if(i >=arr.size())return 0;
if(dp[i][m]!=-1)return dp[i][m];
if(i-1+2*m >=arr.size())return arr[i];
int opponentCanTake = INT_MAX;
for(int x =1;x<=2*m;x++){
opponentCanTake = min(opponentCanTake,solve(arr,i+x,max(x,m),dp));
}
dp[i][m] = arr[i] - opponentCanTake;
return dp[i][m];
}
};
main(){
vector<int> v = {2,7,9,4,4};
Solution ob;
cout <<(ob.stoneGameII(v));
}[2,7,9,4,4]
输出结果
10