LeetCode 1563. 石子游戏 V（DP）
LeetCode 1563. 石子游戏 V（DP）
Michael阿明
发布于 2021-02-19 11:34:59
发布于 2021-02-19 11:34:59
文章被收录于专栏：Michael阿明学习之路
文章目录
1. 题目
几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。
游戏中的每一轮：
Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）； Bob 负责计算每一行的值，即此行中所有石子的值的总和。 Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。 如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。
只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。
返回 Alice 能够获得的最大分数 。
示例 1：
输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。
左行的值是 11 ，右行的值是 14 。
Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。
这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。
Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。
游戏结束，因为这行只剩下一块石头了。
示例 2：
输入：stoneValue = [7,7,7,7,7,7,7]
输出：28
示例 3：
输入：stoneValue = [4]
输出：0
提示：
1 <= stoneValue.length <= 500
1 <= stoneValue[i] <= 10^6来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/stone-game-v 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 区间DP
在这里插入图片描述
时间复杂度O(n3) ，有点高，需要优化
dp[l][r]表示区间内可以得到的最高分，区间从小往大- 区间增加了，枚举中间分隔点
class Solution {
public:
int stoneGameV(vector<int>& stoneValue) {
int n = stoneValue.size(), i, l, r, mid, suml, sumr;
vector<vector<int>> dp(n,vector<int>(n,0));
vector<int> sum(stoneValue);
for(i = 1; i < n; i++)
sum[i] = sum[i-1] + stoneValue[i];//前缀和
for(int len = 1; len < n; len++)//区间长度
{
for(l = 0; l < n; l++)//左端点
{
r = l+len;//右端点
if(r >= n)
continue;
for(mid = l; mid < r; mid++)//枚举中间节点
{
suml = sum[mid]-(l==0 ? 0 : sum[l-1]);
sumr = sum[r]-sum[mid];
if(suml >= sumr)
dp[l][r] = max(dp[l][r], dp[mid+1][r]+sumr);
if(suml <= sumr)
dp[l][r] = max(dp[l][r], dp[l][mid]+suml);
}
}
}
return dp[0][n-1];
}
};- 不使用 vector，过了
class Solution {
public:
int stoneGameV(vector<int>& stoneValue) {
int n = stoneValue.size(), i, l, r, mid, suml, sumr;
int dp[501][501];
memset(dp,0,sizeof dp);
int sum[501] = {0};
sum[0] = stoneValue[0];
for(i = 1; i < n; i++)
sum[i] = sum[i-1] + stoneValue[i];
for(int len = 1; len < n; len++)
{
for(l = 0; l < n; l++)
{
r = l+len;
if(r >= n)
continue;
for(mid = l; mid < r; mid++)
{
suml = sum[mid]-(l==0 ? 0 : sum[l-1]);
sumr = sum[r]-sum[mid];
if(suml >= sumr)
dp[l][r] = max(dp[l][r], dp[mid+1][r]+sumr);
if(suml <= sumr)
dp[l][r] = max(dp[l][r], dp[l][mid]+suml);
}
}
}
return dp[0][n-1];
}
};1708 ms 10.6 MB
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/08/23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
