DP O(m*n*N) time O(m*n) space python


  • 0
    class Solution(object):
        def findPaths(self, m, n, N, i, j):
            """
            :type m: int
            :type n: int
            :type N: int
            :type i: int
            :type j: int
            :rtype: int
            """
            if N==0:return 0
            res=0
            base=[[0 for _ in range(n)] for _ in range(m)]
            
            def getboundnum(m,n,i,j):
                res=0
                if i==0:res+=1
                if j==0:res+=1
                if i==m-1:res+=1
                if j==n-1:res+=1
                return res
            for r in range(m):
                if r==0 or r==m-1:
                    for c in range(n):
                        base[r][c]=getboundnum(m,n,r,c)
                else:
                    base[r][0]=getboundnum(m,n,r,0)
                    base[r][n-1]=getboundnum(m,n,r,n-1)
            res+=base[i][j]
            for _ in range(1,N):
                mx=[[0 for _ in range(n)] for _ in range(m)]
                for r in range(m):
                    for c in range(n):
                        if r>0:
                            mx[r-1][c]+=base[r][c]
                        if r<m-1:
                            mx[r+1][c]+=base[r][c]
                        if c>0:
                            mx[r][c-1]+=base[r][c]
                        if c<n-1:
                            mx[r][c+1]+=base[r][c]
                res+=mx[i][j]
                res%=1000000007
                base=mx
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.