第300场周赛

这次周赛的第3与第4题均可以用记忆化DFS进行求解，第一次尝试这种强大的方法，是动态规划的底层逻辑演算！记忆化DFS的首条件是出现子问题并且子问题数量有限

通过记忆化搜索可以将时间复杂度从2^N降低至O(N)

6109. 知道秘密的人数

例如这一题的 dfs(i) 为第 i 天发现的秘密的人(包含自己在内)一共可以使得后面多少人知道秘密

我们可以怎样求dfs(i)？他可以由哪几个子问题的结果运算得到？

某个人在第 i 天知道秘密，则对应的传播阶段为 [min(i+delay,n),min(i+forget-1,n)] 记为 [a,b]

此时知道秘密的人数有dfs(i)=1+∑dfs(a,b) 其中1为自己本身

只需要处理好base case和memo，同时注意 i 本身也会忘记 就可以轻松写出来

这种一路dfs到底的写法，利用dfs递归返回的结果进行中间运算的方法称为非回溯型的写法

跟回溯写法的区别就是，回溯类型写法需要找到并保存所有的path

在这里我们只需要知道dfs(i)的计算值即可，因此这里dfs(i)带上返回参数int类型

class Solution {
    int n, delay, forget;
    int MOD = (int) 1e9 + 7;
    int[] memo;

    public int peopleAwareOfSecret(int _n, int _delay, int _forget) {
        /*
        Java 记忆化搜索:
        我们记dfs(i)为第i天发现的秘密的人包含自己在内一共可以使得后面多少人知道秘密
        i从i+delay天起,到i+forget-1天都是可以将秘密散播出去的
        也就是[min(i+delay,n),min(i+forget-1,n)]=[a,b]这个时间段是i的传播阶段
        此时知道秘密的人数有1+∑dfs(a,b)
        同时应该注意知道了秘密的人会忘记秘密,因此也会有一个期限
        这里由于子问题的出现可以使用记忆化减少搜索次数
         */
        n = _n;
        delay = _delay;
        forget = _forget;
        memo = new int[n + 1];
        return dfs(1);
    }

    private int dfs(int i) {
        // 在第n天之后才能传播,说明只有自己知道
        if (i + delay > n) return 1;
        // 已经搜索过直接返回
        if (memo[i] != 0) return memo[i];
        // i传播的范围为[min(i+delay,n),min(i+forget-1,n)]=[a,b]
        int a = i + delay, b = Math.min(i + forget - 1, n);
        long res = i + forget <= n ? 0 : 1;    // 自身到[i+forget]就忘记了,在n天内忘记了取0,反之取1
        // 合法的传播范围为[a,b]
        for (int j = a; j <= b; j++) {
            int t = dfs(j);
            memo[j] = t;    // 标记
            res = (res + t) % MOD;
        }
        return (int) res;
    }
}

LC6110. 网格图中递增路径的数目

这道题一样时可以利用子问题的搜索结果减少计算量的题目

dfs(i,j)主逻辑:grid[i][j]出发的递增路径数=本身自成1条路径+上下左右出发严格递增路径数之和

另外用一个memo[i][j]保存从grid[i][j]出发的递增路径数

另外有一些细节：vis的标记方法与撤回、memo的标记方法（怎样才做到不重复标记）、取模技巧（可能溢出的变量要用long类型）等等…

class Solution {
    int[][] memo, grid;
    boolean[][] vis;
    int m, n;
    int MOD = (int) 1e9 + 7;
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int countPaths(int[][] _grid) {
        /*
        dfs记忆化搜索:
        从每个格子出发搜索递增的路径数有多少
        有上下左右4个方向,合法的方向是比之前格子严格大的
        另外用一个memo[i][j]保存从grid[i][j]出发的递增路径数
        dfs(i,j)主逻辑:grid[i][j]出发的递增路径数=本身自成1条路径+上下左右出发严格递增路径数之和
         */
        grid = _grid;
        m = grid.length;
        n = grid[0].length;
        memo = new int[m][n];
        vis = new boolean[m][n];    // 保存当前路径访问过的格子:回溯形式标记,递归出栈时候会恢复原状
        long res = 0;
        // 统计每一个出发点的递增路径
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                vis[i][j] = true;   // 进入dfs前标记搜索
                res = (res + dfs(i, j)) % MOD;
                vis[i][j] = false;  // 撤回
            }
        }
        return (int) res;
    }

    private int dfs(int i, int j) {
        // 已经搜索过了,直接返回其数值
        if (memo[i][j] != 0) return memo[i][j];
        long res = 1;   // 本身自成一条严格递增路径
        // 一共有4个搜索方向
        for (int[] dir : dirs) {
            int newI = i + dir[0], newJ = j + dir[1];
            // 越界||已经搜索过||大小不符合要求
            if (newI < 0 || newI >= m || newJ < 0 || newJ >= n || vis[newI][newJ] || grid[newI][newJ] <= grid[i][j])
                continue;
            vis[newI][newJ] = true; // 标记搜索
            int t = dfs(newI, newJ);    // 下一点出发点路径数
            vis[newI][newJ] = false;    // 记得撤回访问标记,因为仅需要标记单一路径上的;从另外一点出发可以经过同一条路径
            res = (res + t) % MOD;  // 累加结果
        }
        memo[i][j] = (int) res; // 标记grid[i][j]出发的路径数
        return (int) res;
    }
}

补充：关于base case与memo返回的先后顺序问题

这里建议都先写memo返回，然后再写base case，因为有些base case判断逻辑可能有较大的时间开销。

base case 在前面：69ms

class Solution {
    static int[] nums = new int[318];
    static HashSet<Integer> set = new HashSet<>();
    static int[] memo = new int[100005];  // memo[i]=0表示还没赋值，1表示必输，2表示必赢

    // 预处理出可选状态
    static {
        for (int i = 1; i < 318; i++) {
            int num = i * i;
            nums[i] = num;
            set.add(num);
        }
    }

    public boolean winnerSquareGame(int n) {
        /*
        记忆化DFS(1 <= n <= 10^5)
        我们记dfs(i)为剩余石头为i颗时，当前先手选择者是否可以赢得游戏，若能赢则为true，否则为false
        同时维护一个数据结构memo存储已经计算过的结果:memo[i]是已经计算过的dfs(i)
        我们预处理出一个可选的数目列表nums=[1,4,9,16,25,...]
        base case:
       剩余的石头数字恰好在列表当中出现，那么返回true，当前选择者另一个就没法选了
        dfs主逻辑:思考当前选择者可以做出的选择有哪些?
            显然可以从nums中选择 < 当前剩余石头数目的石头j，而且当前选择者赢得游戏的充要条件是:
            选了石头之后下一个先手的输掉游戏，即dfs(i-j)==false，这么多种选择j中只需要一个为false即可
            于是用||条件进行连接
         */
        return dfs(n);
    }

    private boolean dfs(int i) {
        // base case
        if (set.contains(i)) return true;
        if (memo[i] != 0) return memo[i] == 2;  // 记忆化加速
        for (int j = 1; j < 318 && nums[j] < i; j++) {
            // 后手输了，先手必赢
            if (!dfs(i - nums[j])) {
                memo[i] = 2;
                return true;
            }
            // 后手在这种情况赢了，先手在后面还有机会赢
        }
        // 最后都不提前返回，说明先手必输了
        memo[i] = 1;
        return false;
    }

}

memo 在前面：20ms

class Solution {
    static int[] nums = new int[318];
    static HashSet<Integer> set = new HashSet<>();
    static int[] memo = new int[100005];  // memo[i]=0表示还没赋值，1表示必输，2表示必赢

    // 预处理出可选状态
    static {
        for (int i = 1; i < 318; i++) {
            int num = i * i;
            nums[i] = num;
            set.add(num);
        }
    }

    public boolean winnerSquareGame(int n) {
        /*
        记忆化DFS(1 <= n <= 10^5)
        我们记dfs(i)为剩余石头为i颗时，当前先手选择者是否可以赢得游戏，若能赢则为true，否则为false
        同时维护一个数据结构memo存储已经计算过的结果:memo[i]是已经计算过的dfs(i)
        我们预处理出一个可选的数目列表nums=[1,4,9,16,25,...]
        base case:
       剩余的石头数字恰好在列表当中出现，那么返回true，当前选择者另一个就没法选了
        dfs主逻辑:思考当前选择者可以做出的选择有哪些?
            显然可以从nums中选择 < 当前剩余石头数目的石头j，而且当前选择者赢得游戏的充要条件是:
            选了石头之后下一个先手的输掉游戏，即dfs(i-j)==false，这么多种选择j中只需要一个为false即可
            于是用||条件进行连接
         */
        return dfs(n);
    }

    private boolean dfs(int i) {
        if (memo[i] != 0) return memo[i] == 2;  // 记忆化加速
        // base case
        if (set.contains(i)) return true;
        for (int j = 1; j < 318 && nums[j] < i; j++) {
            // 后手输了，先手必赢
            if (!dfs(i - nums[j])) {
                memo[i] = 2;
                return true;
            }
            // 后手在这种情况赢了，先手在后面还有机会赢
        }
        // 最后都不提前返回，说明先手必输了
        memo[i] = 1;
        return false;
    }

}