62. 不同路径

Input: m = 3, n = 7
Output: 28

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

	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			// 到达 (i,j) 格子的路径数目，等于
			// 到达 上方格子 和 左边格子 路径数之和
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}

	return dp[m-1][n-1]
}


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