带回溯的唯一路径快速求解算法

Question

一个位于XxX网格左上角的机器人正试图到达右下角。机器人可以向上、向下、向左或向右移动，但不能访问同一地点两次。右下角有多少条可能的唯一路径？

对此，快速算法解决方案是什么？我花了大量的时间试图找出一个快速算法来解决这个问题。但还是卡住了。

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-完全的。

这也可以作为枚举自我避免行走在2维。根据维基百科，

然而，如果我们只考虑向积极的方向移动，即。从右到下，它有一个封闭形式的解，^M+NC_M。基本上，移动的总次数总是固定为m+n，其中m，n是到对角线endpoint的笛卡尔距离，我们只需选择m向右或n向下。动态规划解决方案本质上是相同的。