题解 | #不同路径的数目(一)#

动态规划，空间O(min(m,n))，时间O(mn)

行列等价，交换之后不会影响路径数。
当前位置的状态dp[j]由左边和上边的状态相加得来，而这两个状态恰好对应dp[j-1]和dp[j]。

class Solution:
    def uniquePaths(self , m: int, n: int) -> int:
        if m==1 or n==1:
            return 1
        if m < n:                      # 用小的值构建dp数组，空间复杂度O(min(m,n))
            m, n = n, m
        dp = [1 for _ in range(n)]     # 用于存放从上方和左方来的路径数,dp[0]始终为初始值1     
        for i in range(m-1):
            for j in range(1, n):
                dp[j] = dp[j-1] + dp[j]     # 状态转移，当前=左+上
        return dp[j]