不同路径。一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径?。力扣62。
排列组合问题。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)
}
}
执行结果如下: