欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode 5498. 石子游戏 V(DP)

程序员文章站 2022-07-02 19:47:58
文章目录1. 题目2. 解题2.1 区间DP1. 题目几块石子 排成一行 ,每块石子都有一个关联值,关联值为整数,由数组 stoneValue 给出。游戏中的每一轮:Alice 会将这行石子分成两个 非空行(即,左侧行和右侧行);Bob 负责计算每一行的值,即此行中所有石子的值的总和。Bob 会丢弃值最大的行,Alice 的得分为剩下那行的值(每轮累加)。如果两行的值相等,Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。只 剩下一块石子 时,游戏结束。Alice 的分数最初...

1. 题目

几块石子 排成一行 ,每块石子都有一个关联值,关联值为整数,由数组 stoneValue 给出。

游戏中的每一轮:

Alice 会将这行石子分成两个 非空行(即,左侧行和右侧行);
Bob 负责计算每一行的值,即此行中所有石子的值的总和。
Bob 会丢弃值最大的行,Alice 的得分为剩下那行的值(每轮累加)。
如果两行的值相等,Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。

只 剩下一块石子 时,游戏结束。Alice 的分数最初为 0 。

返回 Alice 能够获得的最大分数

示例 1:
输入:stoneValue = [6,2,3,4,5,5]
输出:18
解释:在第一轮中,Alice 将行划分为 [623][455] 。
左行的值是 11 ,右行的值是 14 。
Bob 丢弃了右行,Alice 的分数现在是 11 。
在第二轮中,Alice 将行分成 [6][23] 。
这一次 Bob 扔掉了左行,Alice 的分数变成了 1611 + 5)。
最后一轮 Alice 只能将行分成 [2][3] 。
Bob 扔掉右行,Alice 的分数现在是 1816 + 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 5498. 石子游戏 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 5498. 石子游戏 V(DP)

本文地址:https://blog.csdn.net/qq_21201267/article/details/108185564

相关标签: LeetCode