Algorithm8.2 DFS进阶-TLE情况的解决方案
[TOC]
DFS进阶-TLE情况的解决方案
解决方案
- 「一」通过剪枝缩小搜索范围
- 「二」记忆化搜索 - 添加一个v数组 // dp数组，来记录DFS所有触及到的状态，防止再次访问
- 「其他」DP解决
https://www.luogu.com.cn/problem/P1077
「一」剪枝缩小搜索范围
关键是找清楚搜索维度的变量变化，找清楚哪些是递归进入的变量，哪些。该题一开始就看作的是层上dfs，然后通过l来作为依据进行搜索，l来作为return的依据，写出如下代码：
// 搜索
int cnt, ans;
void dfs(int l) {
if (l == n) { if (cnt == m) ans++;return;}
for (int i = 0; i <= a[l+1]; ++i) { cnt+=i;dfs(l+1);cnt-=i; }
}
可以看到其实cnt，（本来是一个全局变量）也可以写成递归的一个依据，因为进入之前与之后有相反操作，因此优化
int ans;
void dfs(int l, int cnt) {
if (l == n) { if (cnt == m) ans++;return; }
for (int i = 0; i <= a[l+1]; ++i) dfs(l+1, cnt+i);
}
「二」记忆化搜索 - 记录状态，防止重复访问
核心：
用v数组区分递归过来的状态是否来过 // 或者用dp数组记录原来来过这个状态之后计算得到的值，这个状态可能是
- 固定个数的属性：
- 特殊函数递归，然后对于传进来的参数abc，当前的参数a、b、c【整体 // 状态】
- 给四个瓶子互相倒水，每个瓶子的水量abcd，每轮中所有瓶子各自水量a、b、c、d
- 若干个属性：（这种情况就不好记录状态了）
例如素数环中的某个数是否用过【不能称得上状态】=> 应该是当前面的若干个数已经排好的，这个整体是状态，然后后面未知的可以直接套用前面的
详细：
- 搜索的过程中重复搜索，然后将重复的放在数组中储存起来，在再次递归进来之后直接返回即可。
- 在返回的时候要详细到递归进来的多个参数的情况。
- 根据参数情况写出dp数组（也就是记忆化数组d）
- 状态转移方程要根据实际情况，用
i j k等参数来逐渐覆盖。 - 对上一个状态转移方程中涉及到的
i j k等参数利用循环来进行遍历。
https://www.luogu.com.cn/problem/P1464
题目大意：纯粹的重复递归调用，极限的话20 * 20 * 20次不同的计算要被一直算，如果可以记录下来，那么这么多次运算只需要算一遍。
注意return的时候，看看边界条件，特判条件放在前面先return；递归条件放后面return
#include <iostream>
using namespace std;
#define maxn 25
typedef long long ll;
ll ta, tb, tc, dp[maxn][maxn][maxn];
ll dfs(int a, int b, int c) {
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return dfs(20, 20, 20);
if (dp[a][b][c]) return dp[a][b][c];
if (a < b && b < c) return dp[a][b][c] = dfs(a, b, c-1) + dfs(a, b-1, c-1) - dfs(a, b-1, c);
else return dp[a][b][c] = dfs(a-1, b, c) + dfs(a-1, b-1, c) + dfs(a-1, b, c-1) - dfs(a-1, b-1, c-1);
}
int main() {
while (scanf("%lld%lld%lld", &ta, &tb, &tc) && !(ta==-1 && tb==-1 && tc==-1))
printf("w(%lld, %lld, %lld) = %lld\n", ta, tb, tc, dfs(ta, tb, tc));
return 0;
}
https://www.luogu.com.cn/problem/P1215
题目大意：三个桶，abc，c满的，来回倒（每次都要倒到 再也倒不出 或者 再也倒不进），问当a空的情况下c有多少。
参数：abc三个桶各自的当前容量，递归往下给进行倒，递归回来自动退回，倒回去了。
状态：对于每一个桶内的量，用一个
v[][]来判断当前这种情况是否来回已经倒过一次了
#include <iostream>
using namespace std;
int a, b, c, na, nb, nc, vis[25];
// 优化dfs
int v[25][25][25];
void dfs(int x, int y, int z) {
if (!x && !vis[z]) vis[z] = 1;
if (v[x][y][z]) return;
v[x][y][z] = 1;
if (x) {
if (y < b) {
if (x > b-y) dfs(x-(b-y), b, z);
else dfs(0, y+x, z);
}
if (z < c) {
if (x > c-z) dfs(x-(c-z), y, c);
else dfs(0, y, z+x);
}
}
if (y) {
if (x < a) {
if (y > a-x) dfs(a, y-(a-x), z);
else dfs(x+y, 0, z);
}
if (z < c) {
if (y > c-z) dfs(x, y-(c-z), c);
else dfs(x, 0, z+y);
}
}
if (z) {
if (x < a) {
if (z > a-x) dfs(a, y, z-(a-x));
else dfs(x+z, y, 0);
}
if (y < b) {
if (z > b-y) dfs(x, b, z-(b-y));
else dfs(x, y+z, 0);
}
}
}
int main() {
scanf("%d%d%d", &a, &b, &c);
na = 0, nb = 0, nc = c;vis[c] = 1;
dfs(0, 0, c);
for (int i = 0; i <= 21; ++i)
if (vis[i]) printf("%d ", i);
return 0;
}
「三」DP解决
https://www.luogu.com.cn/problem/P1025
题目大意：组合数【若干个数相加 组合成目标数】的方案总数
解题思路：首先纯暴力DFS会
- 「一」通过DFS+剪枝，在搜索的过程中减少搜索范围 => AC，但是558ms
- 「三」DP解决 => 13ms
「一」DFS+剪枝
void dfs(int last, int l, int val){
if (l == n) {if (val == total) ans++; return;}
for (int i = last; val+i*(n-l)<=total; ++i) dfs(i, l+1, val+i);
}
「三」利用dp实现
- 定义dp数组：
dp[k][j]表示在第k个数且和为j的时候总方案数 - 状态转移方程：
- 结构：遍历第k个数，第k个数要选i作为储存的值，j作为容量。
dp[k][j] += dp[k-1][j-i]
- 外层循环？？？：
遍历的三个维度，分别为要算进去的数的数值i和要算进去的数的数量k和要填充的其他位置的dp数组的值
// 伪代码
for (i ~ (1, M))
for (j ~ (i, M))
for (k ~ (1, n))
dp[k][j] += dp[k-1][j-i];
// AC代码
dp[0][0] = 1; // 首先初始化一下
for (int i = 1; i <= total; ++i) // 遍历第一维度的时候就不会再涉及到初始化的那个维度，不然会覆盖掉
for (int j = i; j <= total; ++j)
for (int k = 1; k <= n; ++k)
dp[k][j] += dp[k-1][j-i];
https://www.luogu.com.cn/problem/P1586
题目大意：组合数【小于等于4个数平方的和 组合成目标数】 的方案总和
解题思路：
- 「一」DFS+剪枝，会TLE
- 「三」DP解决 => AC
「一」DFS暴搜，但是会TLE。(有使用剪枝，剪枝的思路就是搜索的话，允许当前数重复，但是不允许往前到倒着搜。所以把当前搜的这个数last往下传，到下一层的遍历就要在这层基础上进行搜索)
void dfs(int last, int l, int val) {
if (val == a) {ans++;return;}
if (l >= 4) return;
for (int i = last; i <= sqrt(a-val); ++i) dfs(i, l+1, val+i*i);
}
「三」DP：通过确定了需要两给维度，选择的数的个数和当前所有选择的数的总和作为dp的两个维度=>
- 定义dp数组：
dp[i][j]表示在决策第i个数，并且累加的总和为j的方案总数 - 状态转移方程：
- 结构：遍历第k个数，第k个数要选i作为储存的值，j作为容量。
dp[k][j]++dp[k-1][j-i*i]。
- 外层循环？？？：
for (i*i ~ (0, m))
for (j ~ (i*i, m))
for (k ~ (1, 4))
dp[k][j] += dp[k-1][j-i*i];// 对于dfs的转换就是把原来没有规则的搜索直接通过遍历，给提前算好了，摆在数组里，供使用
// AC代码
dp[0][0] = 1;
for (int i = 1; i*i <= M; ++i) // 遍历第一维度的时候就不会再涉及到初始化的那个维度，不然会覆盖掉
for (int j = i*i; j <= M; ++j)
for (int k = 1; k <= 4; ++k)
dp[k][j] += dp[k-1][j-i*i];
https://www.luogu.com.cn/problem/P1466
题目大意：组合数【不限个数 组合成目标数】的方案总和
「一」DFS暴搜，但是会TLE。
「三」DP解决
- 定义dp数组：
dp[i][j]表示在决策第i个数，并且累加的总和为j的方案总数 - 状态转移方程：
- 结构：在决策第i个数的时候，他的方案总数等于决策上一个数的情况下，选取这个数和不选取这个数的情况和。
- 写法：
dp[i][j]=dp[i-1][j]+dp[i-1][j-i]
- 外层循环：遍历所有的数，遍历到某数的时候就是对该数做决策的时候，需要类似背包，从上限容量一直往下遍历填充
for (i ~ (1, N))
for (j ~ (i, M))
dp[i][j] = dp[i-1][j]+dp[i-1][j-i]
// AC代码
dp[1][1]=1;
for (int i = 2; i <= n; ++i)
for (int j = 0; j <= nn/2; ++j)
if (j > i) dp[i][j] = dp[i-1][j]+dp[i-1][j-i];
else dp[i][j] = dp[i-1][j];