365天挑战LeetCode1000题——Day 106 石子游戏 I - V
石子游戏 I
代码实现
class Solution {
public:
bool stoneGame(vector<int>& piles) {
int n = piles.size();
vector<vector<int>> dp(n, vector<int>(n));
for (int i = 0; i < n; i ) {
dp[i][i] = piles[i];
}
for (int i = n - 2; i >= 0; i--) {
for (int j = i 1; j < n; j ) {
dp[i][j] = max(piles[i] - dp[i 1][j], piles[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1];
}
};
石子游戏 II
代码实现
class Solution {
public:
int stoneGameII(vector<int>& piles) {
int n = piles.size();
vector<int> sum(n 1, 0);
for (int i = 1; i <= n; i ) {
sum[i] = sum[i - 1] piles[i - 1];
}
vector<vector<int>> dp(n 1, vector<int>(n 1));
for (int i = 0; i <= n; i ) {
for (int j = i; j <= n; j ) {
dp[i][j] = sum[n] - sum[n - i];
}
}
for (int i = 1; i <= n; i ) {
for (int j = 1; j <= n; j ) {
for (int k = 1; k <= 2 * j && k <= i; k) {
dp[i][j] = max(dp[i][j], sum[n] - sum[n - i] - dp[i - k][min(max(k, j), n)]);
}
}
}
return dp[n][1];
}
};
石子游戏 III
代码实现
class Solution {
public:
string stoneGameIII(vector<int>& stoneValue) {
int n = stoneValue.size();
if (n == 1) return stoneValue[0] > 0 ? "Alice" : (stoneValue[0] == 0 ? "Tie" : "Bob");
vector<int> sum(n 1);
for (int i = 1; i <= n; i ) {
sum[i] = sum[i - 1] stoneValue[i - 1];
}
vector<vector<int>> dp(n 1, vector<int>(4, INT_MIN));
for (int i = 0; i <= 2; i ) {
for (int j = 1; j <= 3; j ) {
dp[i][j] = sum[min(n - i j, n)] - sum[n - i];
}
}
// 还剩下i个石头
for (int i = 3; i <= n; i ) {
// 选择走j步
for (int j = 1; j <= 3; j ) {
// 选取最大值
// cout << i << " " << j << " " << k << endl;
dp[i][j] = max(dp[i][j],
sum[n] - sum[n - i] - max(dp[i - j][1], max(dp[i - j][2], dp[i - j][3])));
}
}
int ans = max(dp[n][1], max(dp[n][2], dp[n][3]));
if (ans * 2 > sum[n]) return "Alice";
else if (ans * 2 == sum[n]) return "Tie";
else return "Bob";
}
};
石子游戏 IV
代码实现
class Solution {
public:
bool winnerSquareGame(int n) {
// 定义状态dp[i],表示还剩i个石子时的胜利情况
vector<bool> dp(n 1, false);
dp[0] = false;
for (int i = 1; i * i <= n; i ) {
dp[i * i] = true;
}
for (int i = 2; i <= n; i ) {
for (int j = 1; j * j <= i; j ) {
dp[i] = dp[i] || !dp[i - j * j];
}
}
return dp[n];
}
};
石子游戏 V
代码实现
class Solution {
public:
int stoneGameV(vector<int>& stoneValue) {
// dp[i][j],当序列为[i, j]时,Alice能拿到的最大分数
int n = stoneValue.size();
vector<int> sum(n 1);
for (int i = 1; i <= n; i ) {
sum[i] = sum[i - 1] stoneValue[i - 1];
}
int left, total, i, j, k;
int dp[501][501];
memset(dp, 0, sizeof(dp));
// vector<vector<int>> dp(n 1, vector<int>(n 1));
for (i = n - 1; i >= 1; i--) {
for (j = i 1; j <= n; j ) {
total = sum[j] - sum[i - 1];
for (k = i; k < j; k ) {
left = sum[k] - sum[i - 1];
if (left * 2 < total) {
dp[i][j] = max(dp[i][j], left dp[i][k]);
}
else if (left * 2 == total) {
dp[i][j] = max(max(dp[i][j], left dp[i][k]),
left dp[k 1][j]);
}
else {
dp[i][j] = max(dp[i][j], total - left dp[k 1][j]);
}
}
//cout <<"dp["<<i<<"]"<<"["<<j<<"]:"<<dp[i][j] << endl;
}
}
return dp[1][n];
}
};
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggbffj
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01