一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下思路：将该问题转换为：走m-1 步1，走n-1步0，所有的排列组合：
即 m-1 个A和 n-1个B的排列组合数：
采用推导法：已知 m-1 个A和 n-1个B的排列组合数 ，那么根据 m-1 个A和 n-1个B的排列组合数 推导m个A，n个B的排列组合数。
(1) 当有m个A和n个B时，总的排列数为(m+n)!/m!/n!;
(2) 由于不知道m和n哪个大，故两个值都减1，最后知道m和n中其中一个为0；
(3) 当有m-1个A和n-1个B时，总的排列数为(m+n-2)!/(m-1)!/(n-1)!;
(4)这样两个的关系为：fun(m,n) = fun(m-1,n-1)(m+n)(m+n-1)/m/n;
# @lc app=leetcode.cn id=62 lang=python3
#
# [62] 不同路径
#
# @lc code=start
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
m=m-1
n=n-1
def subuniquePaths(m,n):
if m==0 or n==0:
return 1
else:
return int(subuniquePaths(m - 1 , n - 1)*(m + n)*(m+n-1)/m/n)
return subuniquePaths(m,n)