超超超超级详细的多边形游戏问题分析（动态规划）

@toc

多边形游戏

问题简介

• 首先呢，介绍一下多边形游戏是个什么东东
• 多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。
• 游戏步骤： - 将一条边删除 - 选择一条边E及由E连接的2个顶点V1和V2 - 用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点 - 重复以上步骤，直到所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值

我们的问题是： 根据给定的多边形，计算最高分和最底分

问题分析

• 最优子结构性质 - 这里呢，它是满足最优子结构性质的，我们不做过多的解释，直接看它的求解方法
• 递归求解 - 首先，我们在p(i, j)在opi+s处断开， 最大值记为maxf(i,j,s)，最小值记为minf(i,j,s) - 因为只有加法和乘法，加法比较简单。对于乘法，可能存在负数，所以我们要对所有可能的结果做讨论，为了计算方便，我们可以定义如下表示 a=mi,i+s,0        b=mi,i+s,1 c=mi+s,j-s,0      d=mi+s,j-s,1 - 当opi+s=‘+’ mi,j,0=a+c         mi,j,1=b+d - 当opi+s=‘*’ mi,j,0=min{ac,ad,bc,bd} mi,j,1=max{ac,ad,bc,bd}

- 因此可有如下公式

接下来，就是超超超超级详细的解题步骤

超详细解题步骤

这里，我们举了这样一个栗子

在这里插入图片描述

详细步骤如下

m(1,1,1) = 9

m(1,1,0) = 9

m(2,1,1) = -4

m(2,1,0) = -4

m(3,1,1) = 9

m(3,1,0) = 9

m(4,1,1) = 10

m(4,1,0) = 10

m(5,1,1) = -10

m(5,1,0) = -10

m(1,2) = m(1,1)op(2)m(2,1)

op(2) = "+"

m(1,2,1) = m(1,1,1) + m(2,1,1) = 5

m(1,2,0) = m(1,1,0) + m(2,1,0) = 5

m(2,2) = m(2,1)op(3)m(3,1)

op(3) = "+"

m(2,2,1) = m(2,1,1) + m(3,1,1) = 5

m(2,2,0) = m(2,1,0) + m(3,1,0) = 5

m(3,2) = m(3,1)op(4)m(4,1)

op(4) = "+"

m(3,2,1) = m(3,1,1) + m(4,1,1) = 19

m(3,2,0) = m(3,1,0) + m(4,1,0) = 19

m(4,2) = m(4,1)op(5)m(5,1)

op(5) = "*"

m(4,2,1) = max{m(4,1,1)*m(5,1,1), m(4,1,1)*m(5,1,0), m(4,1,0)*m(5,1,1), m(4,1,0)*m(5,1,0)} = -100

m(4,2,0) = min{m(4,1,1)*m(5,1,1), m(4,1,1)*m(5,1,0), m(4,1,0)*m(5,1,1), m(4,1,0)*m(5,1,0)} = -100

m(5,2) = m(5,1)op(1)m(1,1)

m(5,2,1) = m(5,1,1) + m(1,1,1) = -1

m(5,2,0) = m(5,1,0) + m(1,1,0) = -1

$$m(1,3) = \begin{cases}

m(1,1)op(2)m(2,2)\

m(1,2)op(3)m(3,1)

\end{cases}$$

op(2) = "+"

op(3) = "+"

m(1,3,1) = max{m(1,1,1)+m{2,2,1}, m(1,2,1)+m(3,1,1)} = 14 (m(1,1,1)+m(2,2,1))

m(1,3,0) = min{m(1,1,0)+m{2,2,0}, m(1,2,0)+m(3,1,0)} = 14 (m(1,1,0)+m(2,2,0))

$$m(2,3) = \begin{cases}

m(2,1)op(3)m(3,2)\

m(2,2)op(4)m(4,1)

\end{cases}$$

op(3) = "+"

op(4) = "+"

m(2,3,1) = max{m(2,1,1)+m(3,2,1), m(2,2,1)+m(4,1,1)} = 15 (m(2,1,1)+m(3,2,1))

m(2,3,0) = min{m(2,1,0)+m(3,2,0), m(2,2,0)+m(4,1,0)} = 15 (m(2,1,0)+m(3,2,0))

$$m(3,3) = \begin{cases}

m(3,1)op(4)m(4,2)\

m(3,2)op(5)m(5,1)

\end{cases}$$

op(4) = "+"

op(5) = "*"

m(3,3,1) = max{m(3,1,1)+m(4,2,1), max{m(3,2,1)*m(5,1,1), m(3,2,1)*m(5,1,0), m(3,2,0)*m(5,1,1), m(3,2,0)*m(5,1,0)}} = -91 (m(3,1,1)+m(4,2,1))

m(3,3,0) = min{m(3,1,0)+m(4,2,0), min{m(3,2,1)*m(5,1,1), m(3,2,1)*m(5,1,0), m(3,2,0)*m(5,1,1), m(3,2,0)*m(5,1,0)}} = -190 (m(3,2,1)*m(5,1,1))

$$m(4,3) = \begin{cases}

m(4,1)op(5)m(5,2)\

m(4,2)op(1)m(1,1)

\end{cases}$$

op(5) = "*"

op(1) = "+"

m(4,3,1) = max{max{m(4,1,1)*m(5,2,1), m(4,1,1)*m(5,2,0), m(4,1,0)*m(5,2,1), m(4,1,0)*m(5,2,0)}, m(4,2,1)+m(1,1,1)} = -10 (m(4,1,1)*m(5,2,1))

m(4,3,0) = min{min{m(4,1,1)*m(5,2,1), m(4,1,1)*m(5,2,0), m(4,1,0)*m(5,2,1), m(4,1,0)*m(5,2,0)}, m(4,2,0)+m(1,1,0)} = -91 (m(4,2,0)+m(1,1,0))

$$m(5,3) = \begin{cases}

m(5,1)op(1)m(1,2)\

m(5,2)op(2)m(2,1)

\end{cases}$$

op(1) = "+"

op(2) = "+"

m(5,3,1) = max{m(5,1,1)+m(1,2,1), m(5,2,1)+m(2,1,1)} = -5 (m(5,1,1)+m(1,2,1))

m(5,3,0) = min{m(5,1,0)+m(1,2,0), m(5,2,0)+m(2,1,0)} = -5 (m(5,1,0)+m(1,2,0))

$$m(1,4) = \begin{cases}

m(1,1)op(2)m(2,3)\

m(1,2)op(3)m(3,2)\

m(1,3)op(4)m(4,1)

\end{cases}$$

op(2) = "+"

op(3) = "+"

op(4) = "+"

m(1,4,1) = max{m(1,1,1)+m(2,3,1), m(1,2,1)+m(3,2,1), m(1,3,1)+m(4,1,1)} = 24 (m(1,1,1)+m(1,2,1))

m(1,4,0) = min{m(1,1,0)+m(2,3,0), m(1,2,0)+m(3,2,0), m(1,3,0)+m(4,1,0)} = 24 (m(1,1,0)+m(2,3,0))

$$m(2,4) = \begin{cases}

m(2,1)op(3)m(3,3)\

m(2,2)op(4)m(4,2)\

m(2,3)op(5)m(5,1)

\end{cases}$$

op(3) = "+"

op(4) = "+"

op(5) = "*"

m(2,4,1) = max{m(2,1,1)+m(3,3,1), m(2,2,1)+m(4,2,1), max{m(2,3,1)*m(5,1,1), m(2,3,1)*m(5,1,0), m(2,3,0)*m(5,1,1), m(2,3,0)*m(5,1,0)}} = -95 (m(2,1,1)+m(3,3,1))

m(2,4,0) = min{m(2,1,0)+m(3,3,0), m(2,2,0)+m(4,2,0), min{m(2,3,1)*m(5,1,1), m(2,3,1)*m(5,1,0), m(2,3,0)*m(5,1,1), m(2,3,0)*m(5,1,0)}} = -194 (m(2,1,0)+m(3,3,0))

$$m(3,4) = \begin{cases}

m(3,1)op(4)m(4,3)\

m(3,2)op(5)m(5,2)\

m(3,3)op(1)m(1,1)

\end{cases}$$

op(4) = "+"

op(5) = "*"

op(1) = "+"

m(3,4,1) = max{m(3,1,1)+m(4,3,1), max{m(3,2,1)*m(5,2,1), m(3,2,1)*m(5,2,0), m(3,2,0)*m(5,2,1), m(3,2,0)*m(5,2,0)}, m(3,3,1)+m(1,1,1)} = -1 (m(3,1,1)+m(4,3,1))

m(3,4,0) = min{m(3,1,0)+m(4,3,0), min{m(3,2,1)*m(5,2,1), m(3,2,1)*m(5,2,0), m(3,2,0)*m(5,2,1), m(3,2,0)*m(5,2,0)}, m(3,3,0)+m(1,1,0)} = -181 (m(3,3,0)+m(1,1,0))

$$m(4,4) = \begin{cases}

m(4,1)op(5)m(5,3)\

m(4,2)op(1)m(1,2)\

m(4,3)op(2)m(2,1)

\end{cases}$$

op(5) = "*"

op(1) = "+"

op(2) = "+"

m(4,4,1) = max{max{m(4,1,1)*m(5,3,1), m(4,1,1)*m(5,3,0), m(4,1,0)*m(5,3,1), m(4,1,0)*m(5,3,0)}, m(4,2,1)+m(1,2,1), m(4,3,1)+m(2,1,1)} = -14 (m(4,3,1)+m(2,1,1))

m(4,4,0) = min{min{m(4,1,1)*m(5,3,1), m(4,1,1)*m(5,3,0), m(4,1,0)*m(5,3,1), m(4,1,0)*m(5,3,0)}, m(4,2,0)+m(1,2,0), m(4,3,0)+m(2,1,0)} = -95 (m(4,2,0)+m(1,2,0))

$$m(5,4) = \begin{cases}

m(5,1)op(1)m(1,3)\

m(5,2)op(2)m(2,2)\

m(5,3)op(3)m(3,1)

\end{cases}$$

op(1) = "+"

op(2) = "+"

op(3) = "+"

m(5,4,1) = max{m(5,1,1)+m(1,3,1), m(5,2,1)+m(2,2,1), m(5,3,1)+m(3,1,1)} = 4 (m(5,1,1)+m(1,3,1))

m(5,4,0) = min{m(5,1,0)+m(1,3,0), m(5,2,0)+m(2,2,0), m(5,3,0)+m(3,1,0)} = 4 (m(5,1,0)+m(1,3,0))

$$m(1,5) = \begin{cases}

m(1,1)op(2)m(2,4)\

m(1,2)op(3)m(3,3)\

m(1,3)op(4)m(4,2)\

m(1,4)op(5)m(5,1)

\end{cases}$$

op(2) = "+"

op(3) = "+"

op(4) = "+"

op(5) = "*"

m(1,5,1) = max{m(1,1,1)+m(2,4,1), m(1,2,1)+m(3,3,1), m(1,3,1)+m(4,2,1), max{m(1,4,1)*m(5,1,1), m(1,4,1)*m(5,1,0), m(1,4,0)*m(5,1,1), m(1,4,0)*m(5,1,0)}} = -86 (m(1,1,1)+m(2,4,1))

m(1,5,0) = min{m(1,1,0)+m(2,4,0), m(1,2,0)+m(3,3,0), m(1,3,0)+m(4,2,0), min{m(1,4,1)*m(5,1,1), m(1,4,1)*m(5,1,0), m(1,4,0)*m(5,1,1), m(1,4,0)*m(5,1,0)}} = -240 (m(1,4,1)*m(5,1,1))

$$m(2,5) = \begin{cases}

m(2,1)op(3)m(3,4)\

m(2,2)op(4)m(4,3)\

m(2,3)op(5)m(5,2)\

m(2,4)op(1)m(1,1)

\end{cases}$$

op(3) = "+"

op(4) = "+"

op(5) = "*"

op(1) = "+"

m(2,5,1) = max{m(2,1,1)+m(3,4,1), m(2,2,1)+m(4,3,1), max{m(2,3,1)*m(5,2,1), m(2,3,1)*m(5,2,0), m(2,3,0)*m(5,2,1), m(2,3,0)*m(5,2,0)}, m(2,4,1)+m(1,1,1)} = -5 (m(2,1,1)+m(3,4,1))

m(2,5,0) = min{m(2,1,0)+m(3,4,0), m(2,2,0)+m(4,3,0), min{m(2,3,1)*m(5,2,1), m(2,3,1)*m(5,2,0), m(2,3,0)*m(5,2,1), m(2,3,0)*m(5,2,0)}, m(2,4,0)+m(1,1,0)} = -185 (m(2,1,0)+m(3,4,0))

$$m(3,5) = \begin{cases}

m(3,1)op(4)m(4,4)\

m(3,2)op(5)m(5,3)\

m(3,3)op(1)m(1,2)\

m(3,4)op(2)m(2,1)

\end{cases}$$

op(4) = "+"

op(5) = "*"

op(1) = "+"

op(2) = "+"

m(3,5,1) = max{m(3,1,1)+m(4,4,1), max{m(3,2,1)*m(5,3,1), m(3,2,1)*m(5,3,0), m(3,2,0)*m(5,3,1), m(3,2,0)*m(5,3,0)}, m(3,3,1)+m(1,2,1), m(3,4,1)+m(2,1,1)} = -5 (m(3,1,1)+m(4,4,1))

m(3,5,0) = min{m(3,1,0)+m(4,4,0), min{m(3,2,1)*m(5,3,1), m(3,2,1)*m(5,3,0), m(3,2,0)*m(5,3,1), m(3,2,0)*m(5,3,0)}, m(3,3,0)+m(1,2,0), m(3,4,0)+m(2,1,0)} = -185 (m(3,3,0)+m(1,2,0))

$$m(4,5) = \begin{cases}

m(4,1)op(5)m(5,4)\

m(4,2)op(1)m(1,3)\

m(4,3)op(2)m(2,2)\

m(4,4)op(3)m(3,1)

\end{cases}$$

op(5) = "*"

op(1) = "+"

op(2) = "+"

op(3) = "+"

m(4,5,1) = max{max{m(4,1,1)*m(5,4,1), m(4,1,1)*m(5,4,0), m(4,1,0)*m(5,4,1), m(4,1,0)*m(5,4,0)}, m(4,2,1)+m(1,3,1), m(4,3,1)+m(2,2,1), m(4,4,1)+m(3,1,1)} = 40 (m(4,1,1)*m(5,4,1))

m(4,5,0) = min{min{m(4,1,1)*m(5,4,1), m(4,1,1)*m(5,4,0), m(4,1,0)*m(5,4,1), m(4,1,0)*m(5,4,0)}, m(4,2,0)+m(1,3,0), m(4,3,0)+m(2,2,0), m(4,4,0)+m(3,1,0)} = -86 (m(4,2,0)+m(1,3,0))

$$m(5,5) = \begin{cases}

m(5,1)op(1)m(1,4)\

m(5,2)op(2)m(2,3)\

m(5,3)op(3)m(3,2)\

m(5,4)op(4)m(4,1)

\end{cases}$$

op(1) = "+"

op(2) = "+"

op(3) = "+"

op(4) = "+"

m(5,5,1) = max{m(5,1,1)+m(1,4,1), m(5,2,2)+m(2,3,1), m(5,3,1)+m(3,2,1), m(5,4,1)+m(4,1,1)} = 14 (m(5,1,1)+m(1,4,1))

m(5,5,0) = min{m(5,1,0)+m(1,4,0), m(5,2,0)+m(2,3,0), m(5,3,0)+m(3,2,0), m(5,4,0)+m(4,1,0)} = 14 (m(5,1,0)+m(1,4,0))

至此，终于计算完毕，那么：

max = max{m(1,5,1), m(2,5,1), m(3,5,1), m(4,5,1), m(5,5,1)} = 40

max = min{m(1,5,0), m(2,5,0), m(3,5,0), m(4,5,0), m(5,5,0)} = -240

在这里插入图片描述

最后，是Java代码的实现过程

Java代码实现

package PolygonGame;

public class PolygonGame {

	static int n;  // 边和点个数
	static int minf, maxf; 
	static int[] v;  // 点集
	static char[] op;  // 边集
	static int[][][] m;  // 存放最终计算结果
	static int[] result;  // 存放最大值和最小值
	
	public static void main(String[] args) {
		n = 4;
		// 我的案例是: + -7 + 4 * 2 * 5
		v = new int[] {Integer.MIN_VALUE, -7, 4, 2, 5};
		op = new char[] {' ', '+', '+', '*', '*'};
		m = new int[n + 1][n + 1][2];
		for (int i = 1; i <= n; i++) {
			// m[i][j][1] 表示起点为i，长度为j的最大值
			m[i][1][1] = v[i];
			// m[i][j][0] 表示起点为i，长度为j的最小值
			m[i][1][0] = v[i];
		}
		polyMax();
		System.out.println("最大值: " + result[0] + "\n最小值: " + result[1]);
		
	}
	
	/**
	 * 
	 * @param i: 链的起点
	 * @param s: 断开位置
	 * @param j: 链的长度
	 */
	public static void minMax(int i, int s, int j) {
		int[] e = new int[n + 1];
		// 在op(i+s) 处进行分割
		int a = m[i][s][0],  // 左半部分最小值
			b = m[i][s][1],  // 左半部分最大值
			r = (i + s - 1) % n + 1,  // 取余，防止溢出
			c = m[r][j - s][0],  // 右半部分最小值
			d = m[r][j - s][1];  // 右半部分最大值
		if(op[r] == '+') {
			// 对符号进行判断，加号和乘号的处理方式不同
			minf = a + c;
			maxf = b + d;
		} else {
			// 为乘号
			// maxf=max{ac, ad, bc, bd}
			// minf=min{ac, ad, bc, bd}
			e[1] = a * c;
			e[2] = a * d;
			e[3] = b * c;
			e[4] = b * d;
			minf = e[1];
			maxf = e[1];
			for (int k = 2; k < 5; k++) {
				// 查找最大最小值
				if (minf > e[k])
					minf = e[k];
				if (maxf < e[k])
					maxf = e[k];
			}
		}
	}
	
	public static void polyMax() {
		for(int j = 2; j <= n; j++)  // 总长度遍历
			for(int i = 1; i <= n; i++)
				for(int s = 1; s < j; s++) {  // 断开位置
					// 求m[i][j][1]和m[i][j][0]
					minMax(i, s, j);
					if(m[i][j][0] > minf)
						m[i][j][0] = minf;
					if(m[i][j][1] < maxf)
						m[i][j][1] = maxf;
				}
		result = new int[2];
		result[0] = m[1][n][1];
		result[1] = m[1][n][0];
		for(int i = 1; i <= n; i++) {
			if (result[0] < m[i][n][1]) 
				result[0] = m[i][n][1];
			if (result[1] > m[i][n][0]) 
				result[1] = m[i][n][0];
		}
	}
}

最大值: 33

最小值: -35

好了，到此结束。欢迎大家关注我😀