为什么迷宫问题不能用动态规划解决？ 为什么不能用动态规划算法解决迷宫问题？

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

为什么不能使用动态规划来解决？我们不能存储从给定单元格开始的所有路径字符串吗？ 问题链接

- Sneha Sharma

---

这是一个明确定义的问题吗？老鼠解决迷宫的方式不是有无限多种吗？例如，在第一个迷宫中，如果DRDDRR是有效的解决方案，则DUDRDDRR也是有效的，DUDUDRDDRR也是有效的，以此类推。 - Nick ODell

@NickODell，您不能访问已经访问过的单元格。很抱歉我之前忘记添加了这个限制。现在已经进行了编辑。谢谢。 - Sneha Sharma

Answer 1

DP只有在将问题分解成更小的问题时才起作用。对于大多数DP适用的网格问题，存在一个限制，即您只能向下和向右移动，例如LC #62, Unique Paths。

但在这种情况下，您可以朝四个方向移动，因此不再具有划分子问题的能力。子问题会是什么？对于有限移动版本，它是较小的网格，但当您可以向后移动到先前的区域时，没有更多的“较小网格”的概念，您可以在每次移动后定义。

当然，您可以标记一个单元格为已访问，但从DP的角度来看，那并不是真正意义上的子问题，因为在没有该单元格的网格中获取路径数量的答案有助于构建带有该单元格的网格的答案。

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

这只是一个图论问题，你可以通过全面递归遍历来解决。对于每个堆栈帧，标记已访问的单元格，然后朝四个方向步进，将每个移动添加到到目前为止的移动序列中。每当到达目的地时，将该序列作为下一个结果产生。

- ggorlen