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.