动态规划法----多边形游戏问题

好的，多边形游戏问题是一个经典的动态规划问题。问题描述如下：

有一个$n$个顶点的凸多边形，每个顶点上有一个非负整数权值。现在你和另一个人轮流做游戏，每次可以选择一个顶点并将它与相邻的两个顶点一起删掉，同时获得删掉的三个顶点的权值之和的分数。当所有顶点都被删掉后，获得分数更高的人胜利。假设你和对手都采用最优策略，请问你能否获胜，如果能，最多能获得多少分？

为了解决这个问题，我们可以定义$dp[i][j]$表示在剩下第$i$个到第$j$个顶点时，当前玩家（先手或后手）与对手之间的分数差值。显然，当$i=j$时，$dp[i][j]$等于当前顶点的权值，因为只有一个顶点可以选。当$i<j$时，当前玩家可以选择$i$或$j$作为下一步的顶点，对手会选择剩下的一个顶点。我们可以列出如下的状态转移方程：

$$ dp[i][j] = \max \begin{cases} w[i] - dp[i+1][j] \\ w[j] - dp[i][j-1] \end{cases} $$

其中$w[i]$表示第$i$个顶点的权值。这个方程的意义是，当前玩家可以选择$i$或$j$作为下一步的顶点，如果选择了$i$，则对手将面对剩下第$i+1$个到第$j$个顶点，当前玩家的分数为$w[i]$减去对手的分数，即$w[i]-dp[i+1][j]$；同理，如果选择了$j$，则对手将面对剩下第$i$个到第$j-1$个顶点，当前玩家的分数为$w[j]$减去对手的分数，即$w[j]-dp[i][j-1]$。当前玩家希望分数差值尽量大，因此取两者中的较大值。

最终的答案是$dp[1][n]$，即剩下第1个到第$n$个顶点时，当前玩家与对手之间的分数差值。

时间复杂度为$O(n^2)$。