一个机器人在m×n大小的地图的左上角（起点）。
机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？

备注：m和n小于等于100,并保证计算结果在int范围内

数据范围：0 < n,m \le 1000<n,m≤100，保证计算结果在32位整型范围内
要求：空间复杂度 O(nm)O(nm)，时间复杂度 O(nm)O(nm)
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(min(n,m))O(min(n,m))
int uniquePaths(int m, int n ) {
    //write code here
    // float mul1=1,mul2=1;
    // float i=1,j=1;

    // if(m==1||n==1) return 1;
    // for(i=m;i<=m+n-2;i++)
    // { 
    //     mul1=mul1*i;
    // }
    // printf("%lf\n",mul1);
    // for(j=1;j<=n-1;j++)
    //   {
    //     mul2=mul2*j;
    //   }
     //  printf("%lf\n",mul2);
     //  return mul1/mul2;
    //上面本来是用数学公式(m+n)!/(（m!)*(n!))做的，但是会出现分数;
      if(m==1&&n==1) return 1;
     if(m==1||n==1) return 1;
     if(m==2&&n==2) return 2;
     return  uniquePaths(m,n-1)+uniquePaths(m-1,n);
    //这里是递归，因为m和n均为1的时候途径为1，因此将该部分分离了出来，把n==2,m==2作为递归的终点，
      主要的思想是对于（m,n)的终点可以由（m,n-1)的终点达到，也可以由（m-1，n）的终点达到，
      而这两种途径因为都包含了边缘部分，因此这两部分的途径并不重合，两部分之和即为所求
     // if(m==1||n==1) return 1;
      //return  uniquePaths(m,n-1)+uniquePaths(m-1,n);
    //进一步想，n==2,m==2时也用该递归，因此这里对其上部分递归进行了简化；
    //但因为递归的空间开销大，因此在递归的思路上就有了以下代码：
    int i=0;
    int j=0;
    int count[m][n];
    
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i==0||j==0) count[i][j]=1;
           else count[i][j]=count[i-1][j]+count[i][j-1];
        }
    }
     return count[m-1][n-1];
  


}