62. 不同路径

https://leetcode-cn.com/problems/unique-paths/

解法一：计算组合数

长为m，宽为n，从起点到终点一共m-1+n-1步。从m-1+n-1中选m-1步，剩下的n-1步中再选n-1步即可，公式为C(m-1+n-1, m-1) * C(n-1, n-1)，复杂度O(n)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        res = 1
        total = m-1 + n-1
        #计算组合数
        for i in range(total, m-1, -1):
            res = res * i  #分子累乘
        for j in range(1, n):
            res = res // j  #分母累除
        return res

解法二：dp

观察可知到达(i, j)处只能从左边的(i, j-1)和上边的 (i-1, j)得到，没有别的方式，因此DP方程为P[i][j] = P[i - 1][j] + P[i][j - 1]。边界条件为最左列和最上一行，初始值为1，因为只有1条路到达这些地方。复杂度O（n^2)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        path = [[1]*m for _ in range(n)]  #记录表
        for i in range(1, n):  #从第1行开始
            for j in range(1, m):  #从第1列开始
                path[i][j] = path[i-1][j] + path[i][j-1]
        return path[n-1][m-1]

2020.3.29

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m==1 or n==1:
            return 1
        dp = [[0] * m for _ in range(n)]
        for i in range(1, n):
            dp[i][0] = 1
        for j in range(1, m):
            dp[0][j] = 1
        for i in range(1, n):
            for j in range(1, m):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[n-1][m-1]