题目内容

给定一个$2$行$N$列的矩阵$A$。一个有效路径为从起点($1,1$)出发，经过向上、向下或向右的移动，不重复访问同一个方格，最终到达终点($2,N$)。

现在有两名玩家，他们轮流选择路径上的下一个方格(游戏从第一个玩家选择方格($1,1$)开始)。当路径到达终点($2,N$)时，游戏停止。

思路：动态规划

考虑动态规划，定义$dp[i][j][0/1]$表示移动到了$(i,j)$且第$0/1$个人操作完后的成本，$Min$即代表最小成本，$Max$即代表最大成本。

当从终点向起点求解时，就有向上/下、向左三种方法，根据不同的方法更新$dpMin,dpMax$数组即可。