为什么不能用动态规划解决迷宫中的老鼠问题?

Question

我要讨论的问题是下面这个:

Consider a rat placed at (0, 0) in a square matrix m[ ][ ] of order n and has to reach the destination at (n-1, n-1). 
The task is to find a sorted array of strings denoting all the possible directions which the rat can take to reach the destination at (n-1, n-1). 
The directions in which the rat can move are ‘U'(up), ‘D'(down), ‘L’ (left), ‘R’ (right).
You cannot visit an already visited cell.
Examples: 
Input : N = 4 
1 0 0 0 
1 1 0 1 
0 1 0 0 
0 1 1 1
Output :
DRDDRR
Input :N = 4 
1 0 0 0 
1 1 0 1 
1 1 0 0 
0 1 1 1
Output :
DDRDRR DRDDRR

为什么不能用动态规划求解?我们不能存储给定单元格中的所有路径字符串吗?

问题联系

Answer 1

只有当你能把问题分解成更小的问题时，DP才有效。对于DP处理的大多数网格问题，有一个限制，你只能向下和向右移动，就像LC #62，唯一路径。

但是在这种情况下，你可以在所有4个方向上移动，所以划分子问题的能力不再可用。子问题是什么?对于限制移动的版本，它是较小的网格，但是当你可以向后移动到以前的区域时，就不再有"较小网格"的概念了。您可以在每次移动后定义。

当然，你标记了一个访问过的单元格，但这并不是DP意义上的子问题，在没有单元格的情况下，通过网格的路径数的答案可以帮助你建立一个有单元格的网格的答案。

另一方面，在Unique Paths中，您可以盲目地相信子问题的答案，将其添加到构建更大的答案中，并且永远不需要再次访问网格的该区域。

这只是一个图论问题，你可以用穷举递归遍历来解决。对于每个堆栈帧，标记访问的单元格，然后向所有4个方向移动，将每个移动添加到到目前为止的移动序列中。当您到达目的地时，将该序列作为下一个结果。