数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++石头游戏
假设有两名玩家Alex和Lee，他们玩一个石头堆的游戏。有偶数堆石头排成一排，每堆石头数量为piles[i]。游戏的目标是拥有最多的石头。当石头总数为奇数时，没有平局。Alex先开始，玩家轮流从一排石头的开头或结尾取走整堆石头。直到没有石头堆剩下，拥有最多石头的人获胜。假设Alex和Lee都采取最佳策略，检查Alex是否会赢。例如，如果输入是[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来说是一个获胜的策略，答案为true。
为了解决这个问题，我们将遵循以下步骤：
n := piles数组的大小
创建一个大小为n x n的矩阵dp，创建一个大小为n + 1的数组pre
对于i从0到n – 1
pre[i + 1] := pre[i] + piles[i]
对于l从2到n −
对于i := 0, j := l – 1, j < n, i和j递增1
dp[i, j] := piles[j] + pre[j] – pre[i] – dp[i, j – 1] 和 piles[i] + pre[i + 2] – pre[j] + dp[i + 1, j] 的最大值
当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
更新于：2020年4月30日
466 次浏览
广告