[Brush through LeetCode] 576. Number of paths out of bounds: memorized search & Dynamic Programming

This is the 15th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Topic describes

This is the number of paths on LeetCode 576. Out of bounds, with medium difficulty.

Tag: path DP, Dynamic programming, and memorized search

I give you a grid of size m x n and a ball. The starting coordinate of the ball is [startRow, startColumn].

You can move the ball into adjacent cells in all four directions (and beyond the grid boundaries).

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 bounds.

Because the answer could be very large, return the mod of 109+710^9 + 7109+7.

Example 1:

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

Example 2:

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

Tip:

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

Fundamental analysis

Generally speaking, the simple path DP problem can be solved in the conventional DP way because it can only move in one direction (the path problem of one-dimensional checkerboard) or in two directions (the path problem of two-dimensional checkerboard).

This movement rule means that we don’t go into the same cell twice.

From the point of view of graph theory: if each cell is treated as a point, if we can follow the move rule fromaPosition arrive in one stepbLocation, it indicates that there is aaPoint to thebThe directed edge of theta.

That is to say, in the naive path DP problem, the “one-way” movement rule destine that our graph does not have a loop, is a topological order of directed acyclic graph, so we can use conventional DP means to solve.

Back to the question, the movement rule is four connected, not “one way”, in a certain path out of bounds, we can repeatedly enter a cell, there is a ring.

So we need to do it in a different DP way.

Memorized search

Usually in cases where direct DP is difficult to get started with, we can try writing a “memorized search” version first.

So if you were asked to design a DFS function to solve this problem, how would you design it?

I would design it like this:

int dfs(int x, int y, int k) {}
Copy the code

Focus on a few “variable parameters” and “return values” : (x,y)(x,y)(x,y) for the current location, KKK for the maximum number of steps used, and the return value for the number of paths.

According to the learning of LECTURE 8 of DP-Dynamic Programming, we can determine that the recursive exit is:

1. The current off-board position is reached, indicating that an out-of-bounds path has been found. Return 111;
2. If condition 111 is not met, when the number of remaining steps is 000 (no further steps can be taken), no valid exit path is found, return to 000.

The main logic is to move according to the rules of four unicom. The final answer is DFS (startRow, startColumn, maxMove).

Code:

class Solution {
    int MOD = (int)1e9+7;
    int m, n, max;
    int[][] dirs = new int[] [] {{1.0}, {-1.0}, {0.1}, {0, -1}};
    int[][][] cache;
    public int findPaths(int _m, int _n, int _max, int r, int c) {
        m = _m; n = _n; max = _max;
        cache = new int[m][n][max + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k <= max; k++) {
                    cache[i][j][k] = -1; }}}return dfs(r, c, max);
    }
    int dfs(int x, int y, int k) {
        if (x < 0 || x >= m || y < 0 || y >= n) return 1;
        if (k == 0) return 0;
        if(cache[x][y][k] ! = -1) return cache[x][y][k];
        int ans = 0;
        for (int[] d : dirs) {
            int nx = x + d[0], ny = y + d[1];
            ans += dfs(nx, ny, k - 1);
            ans %= MOD;
        }
        cache[x][y][k] = ans;
        returnans; }}Copy the code

Dynamic programming

Based on our “memorized search”, we can design a two-dimensional array f[][]f[][]f[][] as our DP array:

• The first dimension represents the variable parameter in DFS
  $(x,y)$The corresponding
  $index$. The value range is
  $[0, m*n)$
• The second dimension represents the variable parameters in DFS
  $k$. The value range is
  $[0,max]$

We are in the DP arrayDFSReturn value: number of paths.

According to the dimension design and storage of target values in the DP array, we can know that the “state definition” is:

$f[i][j]$Represents from position
$i$Let’s go. No more steps available
$j$Is the number of paths.

At this point, we have arrived at our “state definition” based only on the signature of the DFS function in the “memorized search.” Next, we need to consider the “transition equation.”

Once we have the “state definition”, we need to derive the “transition equation” from the “last step” :

And since we’re allowed to move in four directions, our last step is to count four neighboring directions as well.

Thus, our state transition equation can be obtained:

Note that the first dimension of the DP array in the transition equation stores the idxidxidx corresponding to (x,y)(x,y)(x,y).

From the transition equation, we find that updating f[I][j]f[I][j] [j]f[I][j] depends on f[x][j−1]f[x][j-1]f[x][j−1], so we need to enumerate the maximum number of moving steps “from small to large” in the transition process.

At this point, we have completed the two major steps to solve the “path planning” problem: “state definition” & “transition equation”.

But that’s not all, we still need some valid values to scroll down.

All you really need is some “valid values” for the initialization state.

Looking at our “transition equation”, we can see that the whole transition process is a cumulative process, and the whole recursion process is meaningless without some valid state (non-zero value) to initialize.

So which values can be used as the initialization state?

Obviously, when we’re already at the edge of the matrix, we can step across the matrix in one step, and that counts as a path.

Also, because we can move in four directions, there are different numbers of paths for different edge cells.

In other words, we need to initialize the edge lattice first and preprocess the number of paths that each edge lattice directly goes out of the matrix.

The goal is for our entire DP process to recurse efficiently.

We can see that the implementation of dynamic programming essentially reverses the problem: the original problem asks us to find the number of paths out of bounds from a particular position on the chessboard. When implemented, we start from the edge at the state and gradually derive the number of out-of-bounds paths back to the starting point.

Code:

class Solution {
    int MOD = (int)1e9+7;
    int m, n, max;
    int[][] dirs = new int[] [] {{1.0}, {-1.0}, {0.1}, {0, -1}};
    public int findPaths(int _m, int _n, int _max, int r, int c) {
        m = _m; n = _n; max = _max;
        int[][] f = new int[m * n][max + 1];
        // Initialize the number of paths on the edge grid
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) add(i, j, f);
                if (j == 0) add(i, j, f);
                if (i == m - 1) add(i, j, f);
                if (j == n - 1) add(i, j, f); }}// Enumerates the number of moves from small to large
        for (int k = 1; k <= max; k++) {
            // Enumerate all "locations"
            for (int idx = 0; idx < m * n; idx++) {
                int[] info = parseIdx(idx);
                int x = info[0], y = info[1];
                for (int[] d : dirs) {
                    int nx = x + d[0], ny = y + d[1];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    int nidx = getIdx(nx, ny);
                    f[idx][k] += f[nidx][k - 1]; f[idx][k] %= MOD; }}}return f[getIdx(r, c)][max];       
    }
    void add(int x, int y, int[][] f) {
        for (int k = 1; k <= max; k++) { f[getIdx(x, y)][k]++; }}int getIdx(int x, int y) {
        return x * n + y;
    }
    int[] parseIdx(int idx) {
        return new int[]{idx / n, idx % n}; }}Copy the code

• Time complexity: a total of M ∗ N ∗ MAXm * n * MAXM ∗ N ∗ Max states need to be transferred, and the complexity is O(M ∗ N ∗ Max)O(M * n * Max)O(M ∗ N ∗ Max)
• Space complexity: O(m∗n∗ Max)O(m * n * Max)O(m∗n∗ Max)

The last

This is article No.576 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.

In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .

In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.