题解 | #NC34 求路径#

一.题目描述：
NC34求路径
题目链接：https://blog.nowcoder.net/detail/0?qurl=/practice/166eaff8439d4cd898e3ba933fbc6358
一个机器人在m×n大小的地图的左上角（起点），机器人每次向下或者向右移动，机器人要到达地图的右下角（终点），机器人有多少种不同的路径从起点走到终点？
二.算法(动态规划)

从图片中我们可以看出来：
(1)行和列为1的时候方案数均为1
(2)当行和列不为1的时候方案数为其上一行的方案数加上其左边那一列的行列数
所以，我们定义一个𝑚×𝑛大小的二维数dp,𝑑𝑝[𝑖][𝑗]表示从起点到达第𝑖行第𝑗列的方案数。

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[105][105];
        for(int i=1;i<=m;i++) dp[i][1]=1;
        for(int j=1;j<=n;j++) dp[1][j]=1;//对行列有一个为1的情况进行初始化
        for(int i=2;i<=m;i++){
            for(int j=2;j<=n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];//对行列没有一个是1的情况进行状态转换
            }
        }
        return dp[m][n];
    }
};

时间复杂度：O(n * n)
空间复杂度：O(n * n)需要开出二维数组来存储路径数
优缺点：效率高，不容易发生溢出

三.算法(数学方法)
从起点走到终点，需要向下走m-1步，向右走n-1步，总共走m+n-2步，我们可以这m+n-2步中选出n-1步向右走(或选出m-1步向下走)，那么最后的方案数就是变成了求组合数 的值了

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long x=m+n-2;
        long long y=n-1;
        long long num=1;
        for (int i=1;i<=y;i++)
        {
            num=num*(x-y+i)/i;//求组合数
        }
        return (int)num;
    }
};

时间复杂度：O(n)
空间复杂度：O(1),不需要额外开空间，直接求出组合数的值
优缺点：需要数学分析，不容易想到，而且在数据大的情况下容易溢出