C++石头游戏II

假设有两个人Alice和Bob，他们正在用一堆石头玩游戏。排成一排的若干堆石头，每堆石头数量为正整数，存储在数组piles[i]中。游戏目标是获得最多石头。Alice先开始，Bob后开始。初始M = 1。每轮，玩家可以选择取走剩余石头中前X堆石头，其中1 <= X <= 2M。然后，设置M = max(M, X)。当没有石头剩余时游戏结束。例如，piles = [2,7,9,4,4]，则输出为10。因为如果Alice一开始取一堆，Bob取两堆，Alice再取两堆，Alice可以得到2 + 4 + 4 = 10堆石头。如果Alice一开始取两堆，Bob可以取剩下的三堆，Alice得到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
• 对于x从1到2m的范围
  • op := op, solve(arr, i + x, max(x, m), dp) 的最小值
• dp[i, m] := arr[i] – op
• 返回dp[i, m]
• 实际方法如下：
• n := piles数组的大小，创建一个大小为n的数组arr
• arr[n - 1] := piles[n – 1]
• 对于i := n – 2到0递减
  • arr[i] := arr[i + 1] + piles[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

Arnab Chakraborty

更新于：2020年4月30日

367 次浏览

开启您的职业生涯

完成课程获得认证

开始学习