c++数据结构题求解！

Question

数据结构学不懂，求解
题目描述
亚历克斯和辛迪，两个学生最近花了一些时间来寻宝。除了废金属外，他们还发现了一些装满旧硬币的盒子。盒子的值不同，现在排列成一行。辛迪提出了一个把宝藏分成两部分的想法。她认为公平的方式是她和亚历克斯轮流，每个人从线的左边或右边选择一个盒子。辛迪是个非常大方的人，让亚历克斯先选。

亚历克斯想看看这个主意是否真的对他有好处。他让你写一个程序来计算他将得到的总价值和辛迪如果他先选了一个盒子会得到多少。你可以确信他们都是非常聪明的，并且总是以这样的方式选择下一个盒子，从而为他们带来最佳的整体个人解决方案。这意味着他们可能不会总是选择当前可用的两个值最高的框，以确保他们以后得到一个值更高的框。

输入输出格式
输入格式
第一行输入整数，表示一些装满旧硬币的盒子，每个整数用一个空格隔开；
输出格式
一行输出整数，表示他将获得的总价值与辛迪首先选择一个盒子将获得的总价值进行比较的结果。

输入输出样例1
输入
7 2
输出
5
解释（可选）
亚历克斯会选7,辛迪会选2，所以结果是7‐2=5。

输入输出样例2
输入
2 7 3
输出
-2
解释（可选）
亚历克斯选择 2 还是 3 并不重要，辛迪会选择7,亚历克斯将得到剩下的盒子，(2+3)‐7=‐2。

说明提示
该函数应该返回alex value–cindy value

Answer 1

参考GPT和自己的思路：

这道题目需要用到动态规划的思想，具体的做法是，维护一个二维的数组 $f[i][j]$，表示当剩下的盒子为 $i$ 到 $j$ 时，先手能够获得盒子总价值减去后手能够获得盒子总价值的最大值。初始状态为 $f[i][i]=a[i]$，表示只剩下一个盒子时，先手获得价值为该盒子的价值，后手获得价值为 $0$。

状态转移方程如下：

$$f[i][j]=\max{a[i]-f[i+1][j],a[j]-f[i][j-1]}$$

其中，$a[i]$ 表示第 $i$ 个盒子的价值。上式表示，当先手选了第 $i$ 个盒子时，他能获得的价值为 $a[i]$ 减去后手在剩余盒子中的最大收益，即 $f[i+1][j]$；同理，当先手选了第 $j$ 个盒子时，他能获得的价值为 $a[j]$ 减去后手在剩余盒子中的最大收益，即 $f[i][j-1]$。

最终的答案即为 $f[1][n]$，其中 $n$ 表示盒子的总数。