Leetcode 576. Out of Boundary Paths (python+cpp)

题目

解法：暴力dfs（TLE）

这边要注意的是，不需要判断当前位置是否被访问过。因为问的是多少条不同的路径，只要开始位置不同，那么路径就不同
dfs写法1：这种写法完全可以，但是如果想要加memorization就不方便了，所以写法2更好

class Solution:def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:def helper(i,j,curr_step):nonlocal countif curr_step>N:return if i<0 or i>=m or j<0 or j>=n:count += 1return helper(i+1,j,curr_step+1)helper(i-1,j,curr_step+1)helper(i,j+1,curr_step+1)helper(i,j-1,curr_step+1)count = 0helper(i,j,0)return count

dfs写法2：

class Solution:def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:def helper(i,j,curr_step):if curr_step>N:return 0if i<0 or i>=m or j<0 or j>=n:return 1return helper(i+1,j,curr_step+1)+helper(i-1,j,curr_step+1)+helper(i,j+1,curr_step+1)+helper(i,j-1,curr_step+1)return helper(i,j,0)

解法2：dfs+memorization

在解法1的第二种写法上稍作修改就可以了

class Solution:def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:def helper(i,j,curr_step):if curr_step>N:return 0if (i,j,curr_step) in memo:return memo[(i,j,curr_step)]if i<0 or i>=m or j<0 or j>=n:return 1memo[(i,j,curr_step)] = (helper(i+1,j,curr_step+1)+helper(i-1,j,curr_step+1)+helper(i,j+1,curr_step+1)+helper(i,j-1,curr_step+1))%Mreturn memo[(i,j,curr_step)]memo = {
    }M = 1000000007return helper(i,j,0)