[TOC]

一、题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2
输出: 3

解释:

从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3
输出: 28

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题算法

1. 组合数

思路：

由于网格中并没有任何障碍物，那么机器人可以任意的向下或向右移动。而抵达目标一共需要走步，其中步向右，步向下。
问有多少种路径，其实就是在问步中，取步向右，一共有多少种组合。当然你说取步向下也是一样的。所以结果就变成了求解或者。
但题目给出的数据，直接使用组合数公式暴力求解很容易导致计算过程中数据溢出。因而这里使用唯一分解定理将每一个因子转化为一串素数的乘积的形式，保证计算过程不会溢出（最终结果溢出不计入考虑范围）。

复杂度分析的话，筛法部分超出能力范围完全不会计算，网上比较常见的说法是。但考虑到我这里直接计算到，认为是常数时间应该是没有问题的。
在唯一分解部分，需要分解的一共是总计个数字。
而单次唯一分解一共需要循环次，每次循环最多的一次也不过次计算（这里的其实非常不严谨，但目前的水平只能分析到这个地步了）。
因而总时间复杂度的一个上界应该是，再严格的分析就超出我能力了，若有大佬会算，还望不吝赐教。

PS：可以利用m与n等价，将复杂度变为。

代码：

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m == 0 || n == 0)
            return 0;
        
        // 将200以下所有的素数统计出来，方便后续计算
        // 因为m+n-2最大为198，所以统计到200绰绰有余
        vector<int> is_prime(200, 1);
        cal_prime(is_prime);
        
        vector<int> factors(is_prime.size(), 0);
        for (auto i = 1; i <= n - 1; ++i)
            decomposition(factors, is_prime, i, -1);
        for (auto i = m; i <= m + n - 2; ++i)
            decomposition(factors, is_prime, i, 1);
        
        auto ans = 1;
        for (auto i = 2u; i < factors.size(); ++i)
            // 组合数一定是整数，所以不会出现负指数的素因子
            if (factors[i] > 0)
                ans *= std::pow(i, factors[i]);
        return ans;
    }
        
    // 筛法求解素数
    void cal_prime(vector<int>& is_prime) {
        for (auto i = 2u; i < is_prime.size(); ++i)
            if (is_prime[i])
                for (auto j = i + i; j < is_prime.size(); j += i)
                    is_prime[j] = 0;
    }
    
    // 分解每个因子
    void decomposition(vector<int>& factors, vector<int>& is_prime, int num, int sign) {
        for (auto i = 2u; i < is_prime.size(); ++i) {
            if (is_prime[i])
                while (num % i == 0) {
                    num /= i;
                    factors[i] += sign;
                }
        }
    }
};

2. 暴力法

思路：

直接通过DFS暴力枚举所有路径，然后统计出能成功抵达重点的路径即可。
一个个网格，每个网格都有向下和向右两种可能的行走方案，因而时间复杂度。
显然的，超时，并且当时便已经无法通过测试案例。

代码：

class Solution {
public:
    int uniquePaths(int m, int n) {
        ans = 0;
        this->m = m;
        this->n = n;
        dfs(0, 0);
        return ans;
    }

    void dfs(int r, int c) {
        if (r == m - 1 && c == n - 1)
            ans++;
        for (auto i = 0; i < 2; ++i)
            if (r + row[i] < m &&
                c + col[i] < n)
                dfs(r + row[i], c + col[i]);
    }

private:
    int row[2] = { 0, 1 };
    int col[2] = { 1, 0 };
    int m, n, ans;
};

3. 动态规划

思路：

解法1太过讨巧，求组合数其他情况未必适用。解法2太过简单粗暴，它模拟了整个行走的过程。
那有没有办法折中一下？速度上可以慢于解法1，但不用模拟行走过程，以达到比解法2更快的效果？

想要不模拟行走过程，那我们程序中应该记录什么呢？
回想一下，我们模拟行走过程，是为了从所有行走路线中，找出可以抵达终点的有效路线。也就是说，行走并不是我们关注的重点，计数才是。

那为何不试试直接计数呢？如果可以通过某种手法直接计算出到达每一个网格所需的步数，然后直接返回到终点网格所需要的步数不就好了？
说干就干！
首先缩小问题规模，如果整个网格只有一行，那么答案应该是什么呢？显然，由于只有一行，那么机器人每一步都只能往右走，因而可以到达该行中每个网格的路线应该都只有1条，即。那么，如果整个网络只有一列呢？同理，到达该列中的每个网格的路线也都应该只有一条，即。
好了，最简单的情况考虑过了，接下来要考虑的是，对于一个普通的网格，抵达每一格的路线一共有多少种呢？
仔细思考一下，对任意的网格，抵达它有两种方式，一种是它的从左侧，另一种是从它的上方，分别对应了机器人的向右走和向下走。所以很明显，抵达它的路径数为抵达它上方网格的路径数与抵达它左侧网格的路径数之和。
记抵达第行列的网格的路径数量为，可得

由于每个网格只计算了一次，且记录了每一个网格的路径数，因而时间复杂度，空间复杂度。

代码：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m);
        for (auto i = 0; i < m; ++i)
            dp[i].resize(n, 1);
        for (auto i = 1; i < m; ++i)
            for (auto j = 1; j < n; ++j)
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
        return dp.back().back();
    }
};

4. 动态规划（内存优化）

思路：

其实仔细观察一下解法3的代码，我们会发现dp过程中只用得到dp[i-1]与dp[i]这两行。而dp[i]是在dp[i-1]的基础上进行的计算，所以其实我们能将dp数组从二维降到一维，将空间复杂度由优化到。

代码：

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