This is the 17th day of my participation in the August Text Challenge.More challenges in August

Difficulty: Medium

Topic describes

You are given a grid of size M x N and a ball. The starting coordinate of the sphere is [startRow, startColumn]. You can move the ball into adjacent cells in four directions (through the grid boundary to reach outside the grid). You can move the ball up to maxMove times.

Given five integers m, n, maxMove, startRow, and startColumn, find and return the number of paths that can move the ball out of the boundary. Because the answer may be very large, return the result mod 109 + 7.

Example 1:

Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0 Output: 6

Example 2:

Input: m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1 Output: 12

Tip:

1 <= m, n <= 50 0 <= maxMove <= 50 0 <= startRow < m 0 <= startColumn < n

Their thinking

  • The most direct way is DFS recursive solution, as long as the bounds, there is a result, return 1return1, otherwise recursive solution. However, in direct recursion, there is a lot of repeated calculation. For example, when considering moving KK steps and moving K-1K −1 steps, one step can choose different positions to go out of the bounds (in fact, more different steps can also be selected). If you want to recurse, you should consider memorizing. Python provides the @lru_cache(None) decorator to implement the memo function, plus the @lru_cache(None) code and execution results below.

  • Another way to think about it is to use dynamic programming, and if you write recursion, you can rewrite it as dynamic programming based on recursion.

If N==0, N==0, then it’s always in bounds, it just returns, there’s no way out of bounds. If N > 0 N > 0, expanded mesh, expanded into a (m + 2) * (N + 2) (m + 2) ∗ (N + 2) grid, the grid position of all the edges are all out and so on all edges are dp [k] [x] [y] = = 1 dp [k] [x] [y] = = 1,

                            if i < 0 or i >= m or j < 0 or j >= n: 
                                return 1
Copy the code

And then if k is equal to 0, if you don’t move, you don’t change the number of options, you just skip it. The last

dp[k][x][y] = (dp[k][x][y] + dp[k-1][x-1][y] + dp[k-1][x+1][y] + dp[k-1][x][y-1] + dp[k-1][x][y+1]) % 1000000007 Dp [k] [x] [y] = (dp [k] [x] [y] + dp [k – 1] [x – 1] [y] + dp [k – 1] [x + 1] [y] + dp [k – 1] [x] [1] y – + dp [k – 1] [x] [y + 1))

Transfer equations correspond to recursive calls

for di, dj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
    count=(count + self.findPaths(m, n, N-1, di, dj)) % 1000000007
Copy the code

This rewrites recursive deep search into dynamic programming. Note that because the grid is expanded at this time, the position of [I +1][j+1][I +1][j+1] needs to be returned when the result is finally returned, and the NN step remains unchanged. The code and execution results are shown below.

Memorization recursion

Def findPaths(self, m: int, n: int, n: int, I: int, j: int) -> paths: self, m: int, n: int, j: int) -> paths: count = 0 if N < 0: return count if i < 0 or i >= m or j < 0 or j >= n: return 1 for di, dj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]: count = (count + self.findPaths(m, n, N-1, di, dj)) % 1000000007 return countCopy the code

Dynamic programming

class Solution: def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int: dp = [[[0]*(n+2) for _ in range(m+2)] for _ in range(N+1)] if N == 0: return 0 for k in range(N+1): for x in range(m+2): for y in range(n+2): if x == 0 or y == 0 or x == m + 1 or y == n + 1: Dp [k][x][y] = 1 else: if k == 0: continue else: Part # is equal to the recursive call dp [k] [x] [y] = (dp [k] [x] [y] + dp [k - 1] [1] x [y] + \ dp [k - 1], [x + 1] [y] + dp [k - 1] [x] [1] y + \ dp [k - 1] [x] [y + 1]) % 1000000007 return dp[N][i+1][j+1]Copy the code