第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;
}

}