Short Python DP


  • 0

    For each position (i, j) we check all of its neighbors, if the neighbor is out of the boundary, we know there is one path, otherwise we add neighbor's current paths number into it.

    class Solution(object):
        def findPaths(self, m, n, N, x, y):
            """
            :type m: int
            :type n: int
            :type N: int
            :type x: int
            :type y: int
            :rtype: int
            """
            dp = [[[0] * n for j in range(m)] for k in range(N+1)]
            for k in range(1,N+1):
                for j in range(n):
                    for i in range(m):
                        dp[k][i][j] = sum(dp[k-1][a][b] if -1<a<m and -1<b<n else 1 \
                                      for a,b in ((i-1,j), (i+1,j), (i,j-1), (i,j+1))) % (10**9 + 7)
            return dp[N][x][y]
    

Log in to reply
 

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