题目描述：
石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。
有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。
鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。
给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。
数据范围：
$2\le n \le 1000, 1\le stones[i] \le 1000$
题解：
设 $dp[i][j]$ 表示区间 $[i,j]$ 所能得到的最大差值。每个人肯定都是以差值最大为目标。
$dp[i][j]$ 从 $dp[i+1][j], dp[i][j - 1]$ 转移过来，很容易得到
每次转移时，减去上一次的差值。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e2 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
int dp[maxn][maxn];
int preSum[maxn] = {};
int stoneGameVII(vector<int> &stones)
{
int n = stones.size();
for (int i = 0; i < n; ++i)
{
preSum[i + 1] = preSum[i] + stones[i];
}
for (int i = 0; i < n - 1; ++i)
{
dp[i][i + 1] = max(stones[i], stones[i + 1]);
}
for (int len = 3; len <= n; ++len)
{
for (int i = 1; i + len - 1 <= n; ++i)
{
int j = i + len - 1;
dp[i][j] = max(preSum[j] - preSum[i] - dp[i + 1][j], preSum[j - 1] - preSum[i - 1] - dp[i][j - 1]);
}
}
return dp[1][n];
}
};
|