The number of incremental paths in the grid graph [dfs reverse path + memory dfs]

Preface

DFS The essence is always violent enumeration , There are often many repeated calculations , As a result, the time complexity soared to the exponential level . And use an array to record the results that have been calculated , Avoid double counting, thereby reducing the waste of time , The essence is space for time , Also known as memory search .

One 、 The number of incremental paths in the grid graph

Two 、 Memory search

package competition.single300;

public class CountPaths {
    
    //  You can walk up, down, left and right , In order to replace coordinates with cycles i/j Transformation of , Therefore, the deviation matrix defined in advance .
    static final int[][] gaps = new int[][]{
    {
    -1, 0}, {
    1, 0}, {
    0, -1}, {
    0, 1}};
    //  In order to make it easy to get the remainder , And the remainder object can be modified uniformly , So use a variable to refer to , Form a primary index .
    static final int mod = (int) 1e9 + 7;
    //  For the convenience of taking the length and width of the lattice , So record the length and width of the lattice with simple variables in advance .
    int m, n;

    public int countPaths(int[][] grid) {
    
        //  Initialize lattice length and width .
        m = grid.length;
        n = grid[0].length;
        //  Remember from the... With an array (i,j) The number of starting routes , Not every time dfs To the deepest point .
        int[][] f = new int[m][n];
        //  Converse thinking , Take each grid as the end , With dfs To find the starting point , And record the path length , That is, the number of paths .（ No more nodes , Is a new path .）
        int ans = 0;
        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                ans += dfs(grid, 1 << 31, i, j, f);
                ans %= mod;
            }
        }
        return ans;
    }

    private int dfs(int[][] grid, int pre, int i, int j, int[][] f) {
    
        //  At the end of recursion , No grid is 0, Backtracking without one more grid +1, Represents a new path .（ The feeling of reverse thinking , The starting point is the last node found recursively .）
        if (i < 0 || j < 0 || i == m || j == n || pre >= grid[i][j]) return 0;
        //  If you end with this grid , You already know the number of incremental paths , Go straight back , No more dfs We did the calculation .（ Space for time ）
        if (f[i][j] != 0) return f[i][j];
        //  No passing   too   This node , There is no backtracking assignment .
        f[i][j] = 1;
        // dfs Find the number of paths .
        for (int[] gap : gaps) {
    
            int ni = i + gap[0], nj = j + gap[1];
            //  Each sub path comes , Add the current grid , Is a new path .
            f[i][j] += dfs(grid, grid[i][j], ni, nj, f);
            //  Prevent overflow due to excessive accumulation 
            f[i][j] %= mod;
        }
        return f[i][j];
    }
}

summary

1） Space for time ,DFS One of the typical optimization methods , Memorize . Of course DFS And pruning + Reduce root depth + Reduce the number of roots and other optimization methods .

reference

[1] LeetCode The number of incremental paths in the grid graph