题目分析

还是老规矩，小伙伴们先思考题解，然后参考下面的代码，如果直接看答案，可能当时会了，下次遇到还是不会的情况，因此做题之前思考是我们必须要经历的过程。

记忆化

因为路径是可以来回走的，如N是4步，那么我向上走，再向下走回到了原点，还剩余2步。如果我向下走再向上走也回到了原点，也剩余两步。同理左右方向也是一样。则相当于从原点出发N为2步，需要计算4次，其实我们只需要计算一次即可，那么就需要记住从原点出发N为2所需要的步骤。

因此一种自顶向下的方法呼之欲出，在某一点(i, j)处，可以走N步，第一步可以向四周前进，剩下可以走N - 1步。因此可得递推关系式和边界条件。
$$f(i, j, N) = \begin{cases} 0 & N = 0 \ 1 & i < 0 || i \ge m || j < 0 || j \ge n \ f(i - 1, j, N - 1) + f(i + 1, j, N - 1) + f(i, j - 1, N - 1) + f(i, j + 1, N - 1) & else \end{cases}$$

在Python中，可以使用lru_cache保存函数运行的结果，其他语言需要写一个字典，其中键为i, j和N，值为f(i, j, N)的结果。运行后将结果保存在字典中，下次运行时直接进行查找，如果在字典中则将其取出。算法的**时间复杂度为$O(mnN)$，空间复杂度为$O(mnN)$**。

from functools import lru_cache


class Solution(object):
    def findPaths(self, m, n, N, i, j):
        @lru_cache(None)
        def dfs(i, j, N):
            if N == 0:
                return 0
            tmp = 0
            for di, dj in direction:
                new_i, new_j = i + di, j + dj
                if 0 <= new_i < m and 0 <= new_j < n:
                    tmp += dfs(new_i, new_j, N - 1)
                else:
                    tmp += 1
            return tmp
        direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        return dfs(i, j, N) % 1000000007

记忆化Python实现

这里给出了一种记忆化的实现方案，算法的思路和上面完全相同，不用lru_cache，而是手动维护一个字典，保存了每一次的计算结果。算法的**时间复杂度为$O(mnN)$，空间复杂度为$O(mnN)$**。

class Solution(object):
    def findPaths(self, m, n, N, i, j):
        def dfs(i, j, N):
            if N == 0:
                return 0
            if (i, j, N) in dic:
                return dic[(i, j, N)]
            tmp = 0
            for di, dj in direction:
                new_i, new_j = i + di, j + dj
                if 0 <= new_i < m and 0 <= new_j < n:
                    tmp += dfs(new_i, new_j, N - 1)
                else:
                    tmp += 1
            dic[(i, j, N)] = tmp
            return tmp
        dic = {}
        direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        return dfs(i, j, N) % 1000000007

DP

动态规划其实也是一种记忆化的方式，动态规划就是保存了之前运行产生的状态，通过状态的传递快速求解出结果。因此这个题目也可以通过动态规划进行求解。

用dp[k][i][j]表示到花费k步，到达(i, j)一共有多少种不同的方法，可以通过dp[k - 1][i - 1][j]向下一步，可以通过dp[k - 1][i + 1][j]向上一步，可以通过dp[k - 1][i][j - 1]向右一步，可以通过dp[k - 1][i][j + 1]向左一步到达。

如果在向上，向下，向左或者向右到达了边界，说明这一步可以通过某个方向到达边界，因此在最终的结果上加上dp[k - 1][i][j]即可。算法的**时间复杂度为$O(mnN)$，空间复杂度为$O(mnN)$**。

class Solution(object):
    def findPaths(self, m, n, N, i, j):
        direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        dp = [[[0 for _ in range(n)] for _ in range(m)] for _ in range(N + 1)]
        dp[0][i][j] = 1
        res = 0
        for k in range(1, N + 1):
            for x in range(m):
                for y in range(n):
                    for dx, dy in direction:
                        new_x, new_y = x + dx, y + dy
                        if 0 <= new_x < m and 0 <= new_y < n:
                            dp[k][new_x][new_y] += dp[k - 1][x][y]
                        else:
                            res += dp[k - 1][x][y]
        return res % 1000000007

逆向思维DP

这种动态规划方法是一种农村包围城市的思想。
上面的算法是通过初始的某个位置，每次向周围进行扩散，如果扩散到边界则加上相应的值。
而这个算法是通过边界向内部进行扩散。

up代表从上向下进行扩散，当i = 0时，说明是从上边界点扩散而来，此时有1种方案，否则，说明不是从上边界点扩散而来，此时有dp[k - 1][i - 1][j]种方案。
down代表从下向上进行扩散，当i = m - 1时，说明是从下边界点扩散而来，此时有1种方案，否则，说明不是从下边界点扩散而来，此时有dp[k - 1][i + 1][j]种方案。
left代表从左向右进行扩散，当j = 0时，说明是从左边界点扩散而来，此时有1种方案，否则，说明不是从左边界点扩散而来，此时有dp[k - 1][i][j - 1]种方案。
right代表从右向左进行扩散，当j = n - 1时，说明是从右边界点扩散而来，此时有1种方案，否则，说明不是从右边界点扩散而来，此时有dp[k - 1][i][j + 1]种方案。

当迭代N次以后，dp[N][i][j]就是在(i, j)这一点，通过N步能够到达边界的方案数。算法的**时间复杂度为$O(mnN)$，空间复杂度为$O(mnN)$**。

class Solution(object):
    def findPaths(self, m, n, N, i, j):
        dp = [[[0 for _ in range(n)] for _ in range(m)] for _ in range(N + 1)]
        for k in range(1, N + 1):
            for x in range(m):
                for y in range(n):
                    up = 1 if x == 0 else dp[k - 1][x - 1][y]
                    down = 1 if x == m - 1 else dp[k - 1][x + 1][y]
                    left = 1 if y == 0 else dp[k - 1][x][y - 1]
                    right = 1 if y == n - 1 else dp[k - 1][x][y + 1]
                    dp[k][x][y] = (up + down + left + right)
        return dp[N][i][j] % 1000000007

刷题总结

虽然这个题目有很多种解法，我最喜欢的还是记忆化的方法，因为在DP中会浪费很多的空间和时间，虽然时空复杂度都是$O(mnN)$，但是记忆化是需要哪些点搜索哪些点，而DP就需要遍历所有的点。如N=1，记忆化只需要搜索当前位置的上下左右四个方向，而DP需要遍历地图上的所有点，i从0遍历到m - 1，j从0遍历到n - 1，对于每个点搜索四个方向。所以时空复杂度相对较高。不过DP方法的思路也是非常好的，可以作为本题的延申算法。