java伪码写出求解多边形游戏的动态规划算法

假设多边形游戏的顶点按逆时针顺序编号为 $1, 2, \ldots, n$，其中 $n$ 为顶点数。设 $f(i,j)$ 表示在顶点 $i$ 到顶点 $j$ 的边组成的子多边形中，先手和后手的最大得分差值，其中 $i,j$ 均为闭区间 $[1,n]$ 中的整数。则原问题的解为 $f(1,n)$。

显然，$f(i,i)=0$。对于 $i<j$，考虑如何计算 $f(i,j)$ 的值：

1. 先手选择左端点 $i$，则后手只能在 $[i+1,j]$ 中选择，此时先手得分为 $a_i$，后手得分为 $f(i+1,j)$，因此 $f(i,j)=a_i-f(i+1,j)$；
2. 先手选择右端点 $j$，则后手只能在 $[i,j-1]$ 中选择，此时先手得分为 $a_j$，后手得分为 $f(i,j-1)$，因此 $f(i,j)=a_j-f(i,j-1)$；
3. 先手选择 $i$ 和 $j$ 中间的某个位置 $k$，则后手必定选择 $i$ 或 $j$ 中的一个，设后手选择了 $i$，则先手得分为 $a_k$，后手得分为 $f(i+1,j)$，因此 $f(i,j)=a_k-f(i+1,j)$；设后手选择了 $j$，则先手得分为 $a_k$，后手得分为 $f(i,j-1)$，因此 $f(i,j)=a_k-f(i,j-1)$。因此，

$$f(i,j)=\max\{a_i-f(i+1,j),a_j-f(i,j-1),a_k-f(i+1,j),a_k-f(i,j-1)\}$$

其中 $k\in [i+1,j-1]$。求解 $f(i,j)$ 的时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$。

以下是Java伪代码实现：