多边形游戏动态规划算法

多边形游戏的动态规划算法一般是基于状态转移的思想。

首先，我们需要定义状态。在多边形游戏中，我们可以将多边形看作一个环形的序列，每个点都可以选择作为起点或终点。因此，可以定义一个状态 $f(i,j,k)$ 表示从点 $i$ 开始，走到点 $j$ 结束，并且所有经过的点中，编号大于 $k$ 的点都没有被经过的最小花费。

接下来，我们需要考虑状态转移。对于当前状态 $f(i,j,k)$，我们可以枚举下一个经过的点 $p$，然后将问题分解为两个子问题：

1. 从 $i$ 走到 $p$ 的最小花费 $f(i,p,k)$；
2. 从 $p$ 走到 $j$ 的最小花费 $f(p,j,p+1)$（这里需要注意，为了避免重复计算，我们将 $k$ 更新为 $p+1$）。

那么当前状态的最小花费就是这两个子问题的和，即 $f(i,j,k)=\min_{p=k+1}^{j-1}\{f(i,p,k)+f(p,j,p+1)\}+cost(i,j)$，其中 $cost(i,j)$ 表示从点 $i$ 走到点 $j$ 的花费。

最后，我们需要考虑边界条件。显然，当 $i=j$ 时，花费为 $0$，即 $f(i,i,k)=0$。

综上所述，多边形游戏的动态规划算法可以描述为：

1. 初始化 $f(i,i,k)=0$；
2. 对于 $i<j$，枚举 $p=k+1,k+2,\ldots,j-1$，计算 $f(i,j,k)=\min_{p=k+1}^{j-1}\{f(i,p,k)+f(p,j,p+1)\}+cost(i,j)$；
3. 最终的答案为 $f(1,n,1)$，其中 $n$ 表示多边形的点数。