2021-09-29：不同路径。一个机器人位于一个 m x n 网格的

package main

import "fmt"

func main() {
    ret := uniquePaths(2, 2)
    fmt.Println(ret)
}

// m 行
// n 列
// 下：m-1
// 右：n-1
func uniquePaths(m int, n int) int {
    right := n - 1
    all := m + n - 2
    o1 := 1
    o2 := 1
    // o1乘进去的个数 一定等于 o2乘进去的个数
    for i, j := right+1, 1; i <= all; i, j = i+1, j+1 {
        o1 *= i
        o2 *= j
        gcd := gcd2(o1, o2)
        o1 /= gcd
        o2 /= gcd
    }
    return o1
}

// 调用的时候，请保证初次调用时，m和n都不为0
func gcd2(m int, n int) int {
    if n == 0 {
        return m
    } else {
        return gcd2(n, m%n)
    }
}