LeetCode 1563. 石子游戏 V(DP)

文章目录1. 题目2. 解题2.1 区间DP

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

LeetCode 1563. 石子游戏 V(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

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
LeetCode 1563. 石子游戏 V(DP)

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

LeetCode 1563. 石子游戏 V(DP)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » LeetCode 1563. 石子游戏 V(DP)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏