这次周赛的第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类型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
int n, delay, forget;
int MOD = (int) 1e9 + 7;
int[] memo;
public int peopleAwareOfSecret(int _n, int _delay, int _forget) {
n = _n;
delay = _delay;
forget = _forget;
memo = new int[n + 1];
return dfs(1);
}
private int dfs(int i) {
if (i + delay > n) return 1;
if (memo[i] != 0) return memo[i];
int a = i + delay, b = Math.min(i + forget - 1, n);
long res = i + forget <= n ? 0 : 1;
for (int j = a; j <= b; j++) {
int t = dfs(j);
memo[j] = t;
res = (res + t) % MOD;
}
return (int) res;
}
}
|
这道题一样时可以利用子问题的搜索结果减少计算量的题目
dfs(i,j)主逻辑:grid[i][j]出发的递增路径数=本身自成1条路径+上下左右出发严格递增路径数之和
另外用一个memo[i][j]保存从grid[i][j]出发的递增路径数
另外有一些细节：vis的标记方法与撤回、memo的标记方法（怎样才做到不重复标记）、取模技巧（可能溢出的变量要用long类型）等等…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| 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) {
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;
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;
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;
return (int) res;
}
}
|
补充：关于base case与memo返回的先后顺序问题
这里建议都先写memo返回，然后再写base case，因为有些base case判断逻辑可能有较大的时间开销。
base case 在前面：69ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class Solution {
static int[] nums = new int[318];
static HashSet<Integer> set = new HashSet<>();
static int[] memo = new int[100005];
static {
for (int i = 1; i < 318; i++) {
int num = i * i;
nums[i] = num;
set.add(num);
}
}
public boolean winnerSquareGame(int n) {
return dfs(n);
}
private boolean dfs(int i) {
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class Solution {
static int[] nums = new int[318];
static HashSet<Integer> set = new HashSet<>();
static int[] memo = new int[100005];
static {
for (int i = 1; i < 318; i++) {
int num = i * i;
nums[i] = num;
set.add(num);
}
}
public boolean winnerSquareGame(int n) {
return dfs(n);
}
private boolean dfs(int i) {
if (memo[i] != 0) return memo[i] == 2;
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;
}
}
|
