c++ - 2 名玩家，pion 在矩阵中移动

Question

我有一个关于 2 位玩家在矩阵中移动的问题。我认为这个问题有一个众所周知的方法，但我没有找到。

有一个m行n列的矩阵。 2名玩家将分别移动一个π介子。 Pion 只能移动 i+1 或 j+1，这意味着只能向右或向下移动。矩阵的最后一行和最后一列用给定值填充。 游戏的目的是到达最后一行或最后一列，在最后一行/列中，第一个玩家想要获得最大值，第二个玩家想要获得最小值。

根据上表，2 名玩家将从 0,0 位置移动 p 子 p。第一个玩家想要触及更大的元素，而第二个玩家想要触及更小的元素。

我的想法:由于玩家会分别移动pion，所以我将表格分开如下

带有 1s 的单元格表示第一位玩家唯一可能的移动，2s 表示仅可能的第二位玩家移动。从这一点开始，我想到了一个动态规划解决方案，但找不到任何解决方案。

感谢任何帮助。

Answer 1

动态规划的状态是(行数，列数)。该值是玩家从该单元格移动所能达到的最高分数。
基本情况:最后一行/列中单元格的分数是固定的。
归纳案例:尝试向右和向下移动并选择最佳选项。