动态规划：62. 不同路径

1、题目描述：


2、题解：
动态规划，此题输入填表格的动态规划，
状态转移方程：
机器人只能向左或者向下，那么，我们创建一个dp[i][j]，令矩阵的元素初始值都为1，从i =1 和j = 1开始，每次都是上边的值dp[i][j-1]+左边的值dp[i-1][j]，

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        #动态规划
        dp = [[1] * n ] * m
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

优化：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        #动态规划，空间优化
        dp = [1] * n
        for i in range(1,m):
            for j in range(1,n):
                dp[j] += dp[j - 1]
        return dp[-1]

3、复杂度：
时间复杂度：都为O(MN)，遍历mn矩阵
空间复杂度：O(M*N),优化后，为O(N)