62.md

解法一

• 28ms
• 87%

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

解法二

• 24ms
• 96%

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

解法三

• 将内存占用减小到O(n)级别
• 24ms
• 96%

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        preLine = [1]*n
        curLine = [1]*n
        for i in range(1,m):
            for j in range(1,n):
                curLine[j] = curLine[j-1] + preLine[j]
            preLine, curLine = curLine, preLine
        return preLine[n-1]

解法四

• 进一步减小内存占用
• 28ms
• 88%
• 不知道为什么，速度反而下降了

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