H取数游戏

设DP[L][R]为区间剩余为[L,R]时，先手按照最优解取数最终的总得分与后手的差。

DP[L][R]的后继状态有两个：

取a[L]后变成 DP[L + 1][R]

取a[R]后变成 DP[L][R - 1]

由于下一步的先手是这一步的后手,所以式子应减掉后继的最优解。

DP[L][R] = max(a[L] - DP[L + 1][R], a[R] - DP[L][R - 1])

观察可知由短区间推长区间，因此外层循环为长度，内层循环为左右下标。

标程节选

for (int i = 1; i <= n; ++i) {
	mx[i][i] = a[i];
}
for (int len = 2; len <= n; ++len) {
	for (int i = 1; i + len - 1 <= n; ++i) {
		int j = i + len - 1;
		mx[i][j] = max(a[i] - mx[i + 1][j], a[j] - mx[i][j - 1]);
	}
}