LeetCode 5498. 石子游戏 V（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

时间复杂度O(n³) ，有点高，需要优化

• 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阿明），一起加油、一起学习进步！

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