62. 不同路径

题目链接：https://leetcode.cn/problems/unique-paths/description/

1, 排列组合

func uniquePaths(m int, n int) int {
	ans := 1
	var x int
	if m<n {
		x = m
	} else {
		x = n
	}

	for i:=0;i <x-1 ;i++{
		ans *= (m+n-2-i)
		ans /= (i+1)
	}
	return ans
}

2, (动态规划) 杨辉三角

func uniquePaths(m int, n int) int {
	C := make([][]int,m+n)
    for i := range C {
        C[i] = make([]int,i+1) // 杨辉三角中：第 i 行有 i+1 个元素
    }
	for i:=0;i<m+n;i++{ //m+n-1+1
		for j:=0;j<=i;j++{
			if j==0 || j==i {
				C[i][j] = 1
			}else{
				C[i][j] = C[i-1][j-1] + C[i-1][j]
			}
		}
	}
	return C[n+m-2][n-1] // 结果是第 m 行第 n 列
}