leetcode_62 不同路径

dfs方法,每一个点为起点的路径个数等于他下方和右方点为起点的路径个数相加.
就是一个从中间向一个方向深入的过程。
由于递归超时,需要记忆化.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        direction=[(0,1),(1,0)]
        di=[[-1]*n for _ in range(m)]


        def dfs(i,j):

            if i==m-1 or j==n-1:

                return 1
            if di[i][j]!=-1:
                return di[i][j]

            di[i][j]= dfs(i+1,j)+dfs(i,j+1)
            return di[i][j]

        return dfs(0,0)

另一种dfs 写法.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        direction=[(0,1),(1,0)]
        dic=[[0]*n for _ in range(m)]

        def dfs(i,j):
            if i==m-1 or j==n-1:
                return 1
            if dic[i][j]!=0:
                return dic[i][j]

            for di in direction:
                x=i+di[0]
                y=j+di[1]
                if 0<=x<m and 0<=y<n:

                    dic[i][j]+=dfs(x,y)

            return dic[i][j]

        return dfs(0,0)

动态规划,从底向上的dfs

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        direction=[(0,1),(1,0)]
        dp=[[0]*n for _ in range(m)]

        for i in range(m):
            dp[i][n-1]=1

        for j in range(n):
            dp[m-1][j]=1

        for i in range(m-2,-1,-1):
            for j in range(n-2,-1,-1):

                dp[i][j]=dp[i+1][j]+dp[i][j+1]

        return dp[0][0]

状态压缩,只用一行

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:

        dp=[ 1 for _ in range(n)]



        for i in range(m-2,-1,-1):
            for j in range(n-2,-1,-1):

                dp[j]=dp[j]+dp[j+1]

        return dp[0]