algorithm - 通过回溯解决唯一路径的快速算法

Question

A robot located at the top left corner of a XxX grid is trying to reach the bottom right corner. The robot can move either up, down, left, or right, but cannot visit the same spot twice. How many possible unique paths are there to the bottom right corner?

对此的快速算法解决方案是什么？我花了很多时间试图找出一个快速算法。但还是卡住了。

这基本上是 unique paths Leetcode problem ，除了回溯。

没有回溯的唯一路径可以用动态规划来解决，例如:

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> cur(n, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                cur[j] += cur[j - 1];
            }
        }
        return cur[n - 1];
    }
};

什么是快速算法解决方案，使用动态规划，唯一路径，回溯除外？对于 10X10 网格，可以快速找到结果 1,568,758,030,464,750,013,214,100 的东西。

Reddit , Wikipedia , 和 Youtube有资源说明这个问题的复杂性。但他们没有任何答案。

Answer 1

问题无法使用动态规划来解决，因为递归关系不会将问题分解为子问题。动态规划假设要计算的状态仅依赖于循环中的子状态。在这种情况下是不正确的，因为可能存在循环，即。上下波动。

这个问题的一般情况，计算有向循环图中简单路径的数量，被认为是#P-Complete .

这也可以作为枚举self avoiding walks在二维中。根据维基百科，

Finding the number of such paths is conjectured to be an NP-hard problem^{[citation needed]}.

但是，如果我们只考虑正方向的移动，即。向右和向下，它有一个封闭形式的解，^m+nC_m。基本上，总移动次数始终固定为 m + n，其中 m、n 是到对角线终点的笛卡尔距离我们只需要选择 m right(s) 或 n down(s)。动态规划的解法本质上是一样的。