2021-09-29：不同路径。一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？。力扣62。

福大大 答案2021-09-29：

排列组合问题。c(m+n-2,m-1)或者c(m+n-2,n-1)。 时间复杂度：O(min(m,n))。 额外空间复杂度：O(1)。

代码用golang编写。代码如下：

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)
    }
}

执行结果如下： 图片

左神java代码