题解 | #求路径#

NC34 求路径

题意分析：

算出从起点到终点的路径数目。

题解一（动态规划）：

假设机器人站在点(i，j)处，其可以从(i-1，j)向下移动一行走到，也可以从向右移动一步走到。因此到达位置(i，j)出路径的数目等于到达位置(i-1，j)的路径数目与达到(i，j-1)的路径数目之和。我们假设dp[i,j]表示到达点(i，j)的路径数目，那么dp[i,j] = dp[i-1,j]+dp[i,j-1]。我们新建一个二维表格dp，计算dp里面每一个值，最后返回目标位置的dp即可。

初始化，第一行和第一列的dp值全部为1，这些位置可以确定只有一条路径。表格的其他位置，根据转移方程，进行填充即可。
如下图，站在红叉的位置，根据规则，其只能从其左边和上面走到，那么到达红叉的走法就是前两步骤的和。
图片说明
代码实现如下：

 int uniquePaths(int m, int n) {
        vector<vector<int>>dp(m,vector<int>(n,0));
        //第一行初始化，只有一条路径
        for(int i=0;i<n;i++){
            dp[0][i] = 1;
        }
        //第一列初始化，只有一条路径
        for(int i=0;i<m;i++){
            dp[i][0] =1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                //转移方程
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];

时间复杂度： $O(mn)$ ，我们循环了m*n次，时间复杂度 $O(mn)$

空间复杂度： $O(mn)$ ,在本题实现中，求解一行中某个位置的值，实际上只用了上一行和该位置左边的元素，因此空间复杂度可以降低为 $(min(n,m))$ 。

方法二：组合数学

思路与算法

由于在矩阵中没有障碍物，从左左上角移动到右下角一共要移动m+n-2次，其中有m-1次向下，n-1次向右，对这两种操作进行组合。因此最后就是求 $C_{m+n-2}^{m-1}$ 这个组合数。

组合公式为 $C_{m+n-2}^{m-1}=\frac{(m+n-2)!}{(m-1)!(n-1)!}=\frac{(m+n-2)*...*n}{(m-1)!}$ ,直接算该值即可。

int uniquePaths(int m, int n) {
    long long ret = 1;
    for (int x = n, y = 1; y < m; ++x, ++y) {
        //组合公式的循环求解
        ret = ret * x / y;
    }
    return ret;
}

时间复杂度： $O(min(m,n))$

空间复杂度： $O(1)$