看到题目知道需要用到DFS，自己写了一版存在重复计算的bug，代码如下：

class Solution {
public:
    int uniquePaths(int m, int n) {
        int res = 0;
        help(0,0,m,n,res);
        return res;
    }
    
    void help(int start_m,int start_n,int m,int n,int &res)
    {
        if(start_m >= m-1 && start_n >= n-1)
            return;
        
        if(start_m < m -1)
        {
            res++;
            help(start_m + 1,start_n,m,n,res);
        }
        
        if(start_n < n-1)
        {
            res++;
            help(start_m ,start_n + 1,m,n,res);
        }
            
    }
};

以3 2为例，输出结果:

Your input
3
2
Output
8
Expected
3

使用动态规划DP,这里由于机器人只能往右 往下，因此走到某个结点，前一步要么从上面要么从左边，因此使用vector模拟二维数组来记录到所有结点路径条数。

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

这里其实不需要m *n的空间复杂度，只需要两行即可，原因是通过上面的代码（res[i][j] = res[i - 1][j] + res[i][j-1];）可以看到计算当前结点路径条数需要上一行和同一行前一列元素，而第一行和第一列元素均为0，因此可以只通过两行元素求解，复杂度降为O(n)
优化后的DP，减少内存占用，代码如下：

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

运行结果:

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Unique Paths.
Memory Usage: 6.4 MB, less than 53.76% of C++ online submissions for Unique Paths.

更进一步优化：

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];
    }
};

这里为什么能这么优化？我们考虑m = 4,n =4场景，手动计算结果：

1 1 1 1
1 2 3 4
1 3 6 10
1 4 10 20
模拟上述代码运行，初始时cur一行全是1，然后前后累加结果：
1 2 3 4(第二行)
接着继续执行前后累加，结果：
1 3 6 10(第三行)
接着继续执行前后累加，结果:
1 4 10 20，即可得到最终结果20