动态规划的多边形游戏

目录

1. 多边形游戏简介
2. 举例以及详细分析
3. 代码块
4. 测试结果

---

多边形游戏简介

问题描述：
单人多边形游戏在一个初始状态由n个顶点构成的封闭图形中展开。每个顶点都被赋值为一个整数；每条边上设置一个运算符，在本游戏中仅限于加法" +" 或乘法" *" 操作。各条边上依次标注编号1至n

游戏第1步，将一条边删除。

随后n-1步按以下方式操作：

(1)选择一条边E以及由E连接着的2个顶点V1和V2；

用一个新顶点替代边E及其相连的两个端点V₁和V₂，并将其赋值为这两个端点进行运算得到的结果

最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。

问题:对于给定的多边形，计算最高得分。

设给定多边形按顺时针方向依次排列的顶点与边分别为 op[1]、v[1]、op[2]、v[2]、…、op[n]、v[n] ，其中 op[i] 表示第 i 条边对应的运算符 ，v[i] 表示第 i 个顶点处的数值 ，i=1~n 。
在给定多边形中 ，以顶点 i (1≤i≤n) 开始计算 ，包含 j 个顶点（即长度为 j 的链）的顺时针链 p(i,j) 可记作：
p(i,j)= v_i, op_{i+1}(v_{i+1}), op_{i+2}(,…, v_{i+j−1});

3. 如果这条链的最后一次合并运算