本文涉及知识点

C++动态规划
数学

LeetCode1690. 石子游戏 VII

石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。
有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。
鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。
给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。
示例 1：
输入：stones = [5,3,1,4,2]
输出：6
解释：

• 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。
• 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。
• 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。
• 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。
• 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。
  得分的差值 18 - 12 = 6 。
  示例 2：
  输入：stones = [7,90,5,1,100,10,10,2]
  输出：122
  提示：
  n == stones.length
  2 <= n <= 1000
  1 <= stones[i] <= 1000

#1690 博弈论 动态规划

动态规划的状态表示

dp[i][j]表示 ，stones[0…i-1]和stones[j+1…]已经移除，当前玩家能获取的最大分数差。空间复杂度：O(nn)

动态规划的转移方程

如果i == j，则dp[i][j]为0。否则：
dp[i][j] =max (preSum[j+1]-preSum[i+1]- dp[i+1][j],preSum[j]-preSum[i]-dp[i][j-1])
时间复杂度：O(nn)

动态规划的初始值

如果i == j，则dp[i][j]为0。

动态规划的填报顺序

len = 2 To n
i = 0 ; i < n;i++
j = i+len-1

动态规划的返回值

dp[0].back()

代码

核心代码

class Solution {
		public:
			int stoneGameVII(vector<int>& stones) {
				const int N = stones.size();
				vector<int> preSum(N + 1);
				partial_sum(stones.begin(), stones.end(),preSum.begin() + 1);
				vector<vector<int>> dp(N, vector<int>(N));
				for (int len = 2; len <= N; len++) {
					for (int i = 0; i + len <= N; i++) {
						const int j = i + len - 1;
						dp[i][j] = max(preSum[j + 1] - preSum[i + 1] - dp[i + 1][j], preSum[j] - preSum[i] - dp[i][j - 1]);
					}
				}
				return dp[0].back();
			}
		};

单元测试

vector<int> stones;
		TEST_METHOD(TestMethod11)
		{
			stones = { 5, 3, 1, 4, 2 };
			auto res = Solution().stoneGameVII(stones);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod12)
		{
			stones = { 7,90,5,1,100,10,10,2 };
			auto res = Solution().stoneGameVII(stones);
			AssertEx(122, res);
		}