C++ 帮助亚历克斯处理宝藏
题目描述
亚历克斯和辛迪，两个学生最近花了一些时间来寻宝。除了废金属外，他们还发现了一些装满旧硬币的盒子。盒子的值不同，现在排列成一行。辛迪提出了一个把宝藏分成两部分的想法。她认为公平的方式是她和亚历克斯轮流，每个人从线的左边或右边选择一个盒子。辛迪是个非常大方的人，让亚历克斯先选。
亚历克斯想看看这个主意是否真的对他有好处。他让你写一个程序来计算他将得到的总价值和辛迪如果他先选了一个盒子会得到多少。你可以确信他们都是非常聪明的，并且总是以这样的方式选择下一个盒子，从而为他们带来最佳的整体个人解决方案。这意味着他们可能不会总是选择当前可用的两个值最高的框，以确保他们以后得到一个值更高的框。
输入输出格式
输入格式
第一行输入整数，表示一些装满旧硬币的盒子，每个整数用一个空格隔开；
输出格式
一行输出整数，表示他将获得的总价值与辛迪首先选择一个盒子将获得的总价值进行比较的结果。
输入输出样例1
输入
7 2
输出
5
解释（可选）
亚历克斯会选7,辛迪会选2，所以结果是7‐2=5。
输入输出样例2
输入
2 7 3
输出
-2
解释（可选）
亚历克斯选择 2 还是 3 并不重要，辛迪会选择7,亚历克斯将得到剩下的盒子，(2+3)‐7=‐2。
说明提示
该函数应该返回alexvalue–cindyvalue
参考GPT和自己的思路：
可以使用DP（动态规划）来解决这个问题。定义一个二维的数组dp，其中dp[i][j]表示当游戏在剩余硬币数为i到j之间时，先手可以获得的最大价值。那么有以下递推公式：
dp[i][j] = max(coin[i] + min(dp[i + 2][j], dp[i + 1][j - 1]), coin[j] + min(dp[i + 1][j - 1], dp[i][j - 2]))
其中coin[i]表示第i个硬币的价值。意思是先手可以选择拿第i个硬币或第j个硬币，然后在剩下的硬币中变为后手，后手在剩下的硬币中也有两种选择，所以要取其中的最小值。最后再减去后手获得的价值，就是先手的净收益。
最终的答案就是dp[0][n-1]，其中n为硬币数量。
参考GPT和自己的思路：
这个问题可以使用动态规划来解决。定义一个二维数组dp，其中dp[i][j]表示从第i个盒子到第j个盒子（包括i和j）的最大价值差（亚历克斯的价值减去辛迪的价值）。初始状态为dp[i][i] = a[i]（其中a[i]表示第i个盒子的价值），其他状态为dp[i][j] = max(a[i]-dp[i+1][j], a[j]-dp[i][j-1])。
解释一下状态转移方程，对于区间[i, j]，亚历克斯有两种选择：选择左端点i或者选择右端点j。如果亚历克斯选择了i，那么辛迪面对的是区间[i+1, j]，辛迪选择完之后亚历克斯面对的区间就变成了区间[i+2, j]，亚历克斯最终获得的价值差就是a[i]-dp[i+1][j]。同理，如果亚历克斯选择了j，那么辛迪面对的是区间[i, j-1]，亚历克斯最终获得的价值差就是a[j]-dp[i][j-1]。在两种选择中，亚历克斯始终选择价值差更大的那个选项。
最终的答案就是dp[1][n]，其中n表示盒子的数量。
C++代码如下：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int a[N], dp[N][N];
int main()
{
int n; cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = n; i; i -- )
for (int j = i; j <= n; j ++ )
if (i == j) dp[i][j] = a[i];
else dp[i][j] = max(a[i]-dp[i+1][j], a[j]-dp[i][j-1]);
cout << dp[1][n] << endl;
return 0;
}