网格图中递增路径的数目[dfs逆向路径+记忆dfs]

前言

DFS本质是一直暴力枚举法，往往存在很多的重复计算，从而导致时间复杂度飙升至指数级别。而用数组记录曾经计算过结果，防止重复计算从而减少时间的浪费，本质就是空间换时间，也称记忆化搜索。

一、网格图中递增路径的数目

二、记忆化搜索

package competition.single300;

public class CountPaths {
    
    // 上下左右都可以走，为了用循环代替坐标i/j的变换，所以采用提前定义好的偏差矩阵。
    static final int[][] gaps = new int[][]{
    {
    -1, 0}, {
    1, 0}, {
    0, -1}, {
    0, 1}};
    // 为了方便取余时写的简单，且可统一修改取余对象，所以用一个变量指代，形成一级索引。
    static final int mod = (int) 1e9 + 7;
    // 为了方便取格子的长宽，所以提前用简单变量记录格子长宽。
    int m, n;

    public int countPaths(int[][] grid) {
    
        // 初始化格子长宽。
        m = grid.length;
        n = grid[0].length;
        // 用数组记住从第(i,j)出发的路径个数，不用每次都dfs到最深处。
        int[][] f = new int[m][n];
        // 逆向思维，以每个格子作为终点，以dfs的方式来寻找起点，并记录路径长度，即路径个数。（没多一个节点，就是一个新路径。）
        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) {
    
        // 递归结束处，无格子就是0，回溯没多一个格子就+1，表示一条新路径。（优点逆向思维的感觉，起点在递归寻找到的最后一个节点。）
        if (i < 0 || j < 0 || i == m || j == n || pre >= grid[i][j]) return 0;
        // 如果以该格子为终点，已经知道递增路径的个数了，就直接返回，不用再dfs进行计算了。（空间换时间）
        if (f[i][j] != 0) return f[i][j];
        // 没有路过 过 这个节点，就没有回溯给其赋值。
        f[i][j] = 1;
        // dfs寻找路径数。
        for (int[] gap : gaps) {
    
            int ni = i + gap[0], nj = j + gap[1];
            // 每条分路径过来，加上当前格子，都是一个新路径。
            f[i][j] += dfs(grid, grid[i][j], ni, nj, f);
            // 防止累计过多而溢出
            f[i][j] %= mod;
        }
        return f[i][j];
    }
}

总结

1）空间换时间，DFS典型的优化方式之一，记忆化。当然DFS还有剪枝+减少根深度+减少根个数等等优化方式。

参考文献

[1] LeetCode 网格图中递增路径的数目