C ++中的石头游戏
假设我们有两个玩家Alex和Lee，他们玩着一堆堆石头。偶数排成一排，每堆有一定数量的石堆[i]。游戏的目标是以最多的石头结束。当石头总数为奇数时，就没有关系了。亚历克斯和李轮流转，亚历克斯先发。在每个回合中，玩家从该行的开头或结尾拿走整堆石头。这将继续进行直到没有更多的桩剩下了，这时拥有最多石头的人获胜。假设亚历克斯和李扮演最佳状态，请检查亚历克斯是否赢得比赛。因此，如果输入像[5,3,4,5]，那么结果将为true，因为Alex首先开始，所以他只能取前5个或后5个。现在，如果他取前5个，那么该行变为[3，4，5]。如果Lee在那之后拿3，则局是[4，5]，而Alex以5赢得10分。当Lee拿到最后5时，局面是[3，4]，Alex拿4赢得9分。因此，这表明前5名是Alex的胜利之举，答案是正确的。
为了解决这个问题，我们将遵循以下步骤-
n：=桩阵列的大小
创建大小为nxn的矩阵dp，创建另一个大小为n+1的数组pre
对于i，范围为0至n–1
pre[i+1]：=pre[i]+桩[i]
对于2到n之间的l-
dp[i，j]：=桩[j]+pre[j]–pre[i]–dp[i，j–1]和桩[i]+pre[i+2]–pre[j]的最大值+dp[i+1，j]
对于i：=0，j：=l–1，j<n，将i和j加1
当dp[0，n–1]>dp[0，n–1]–pre[n]时返回true
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool stoneGame(vector<int>& piles) {
int n = piles.size();
vector < vector <int> > dp(n,vector <int>(n));
vector <int> pre(n + 1);
for(int i = 0; i < n; i++){
pre[i + 1] = pre[i] + piles[i];
}
for(int l = 2; l <= n; l++){
for(int i = 0, j = l - 1; j < n; i++, j++){
dp[i][j] = max(piles[j] + pre[j] - pre[i] - dp[i][j - 1], piles[i] + pre[i + 2] - pre[j] + dp[i + 1][j]);
}
}
return dp[0][n - 1] > dp[0][n - 1] - pre[n];
}
};
main(){
vector<int> v = {5,3,4,5};
Solution ob;
cout << (ob.stoneGame(v));
}输入项
[5,3,4,5]
输出结果
1