0062.不同路径

方法一：动态规划

时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。

func uniquePaths(m int, n int) int {
	dp := make([][]int, m)
	for i := 0; i < m; i++ {
		dp[i] = make([]int, n)
		dp[i][0] = 1
	}
	for i := 0; i < n; i++ {
		dp[0][i] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[m-1][n-1]
}

方法二 ：数学

易知解法数目为：$C_{m+n-2}^{m-1} = \frac{(m+n-2)(m+n-3)···n}{(m-1)!}$，故时间复杂度 $O(m)$，空间复杂度 $O(1)$。

func uniquePaths(m int, n int) int {
	ans := 1
	for i, v := 1, n; i < m; i, v = i+1, v+1 {
		ans = ans * v / i
	}
	return ans
}