dfs写法模板总结

参考博客

必写：

pos: 表示数字的位数

从末位或第一位开始，要根据题目的数字构造性质来选择顺序，一般选择从 a1 到 an 的顺序。初始从 len 开始的话，边界条件应该是 pos=0，限制位数应该是 apos， DFS时 pos−1 ；初始从1 开始的话，边界条件应该是 pos>len，限制位数应该是 alen−pos+1 ， DFS时 pos+1 。两种都可以，看个人习惯。

可选参数：

pre:表示上一个数是多少

有些题目会用到前面的数

lead: 前导零是否存在，lead=1 存在前导零，否则不存在。

一般来说有些题目不加限制前导零会影响数字结构，所以 lead 是一个很重要的参数。 如果 lead=1 且当前位为 0 ，那么说明当前位是前导 0，继续搜索 pos+1，其他条件不变。 如果 lead=1 且当前位不为 00，那么说明当前位是最高位，继续搜索 pos+1，条件变动。 如果 lead=0，则不需要操作。

sum : 搜索到当前所有数字之和

有些题目会出现数字之和的条件

cnt: 某个数字出现的次数

cnt: 某个数字出现的次数 有些题目会出现某个数字出现次数的条件

limit: 可以填数的限制

可以填数的限制（无限制的话(limit=0) 0∼9 随便填，否则只能填到 ai）

不要62

题意： 找到区间 [L,R][L,R] 不能出现 4 和 62 的数的个数

分析： 首先此题不需要 lead，其次有 62 所以要记前驱 pre

 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

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int l, r, dp[N][N], len, a[N];
int dfs(int pos, int pre, int limit) {
    if (!pos) return 1;
    if (!limit && dp[pos][pre] != -1) return dp[pos][pre];
    int res = 0, up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i ++) {
        if (i == 4 || (i == 2 && pre == 6)) continue;
        res += dfs(pos - 1, i, limit && i == up);
    }
    return limit ? res : dp[pos][pre] = res;
}
int cal(int x) {
    memset(dp, -1, sizeof dp);
    len = 0;
    while (x) a[++ len] = x % 10, x /= 10;
    return dfs(len, 0, 1);
}
signed main() {
    while (cin >> l >> r, l || r) {
        cout << cal(r) - cal(l - 1) << endl;
    }
}

题目6：计数问题 题意： 统计区间[L,R] 出现 0123456789的各个数字总次数

分析： 需要用到 lead，需要用到次数总和 sum，还有哪个数字 num。基本上可以套模板，注意边界条件。

 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

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int l, r, len, a[N], dp[N][N];
int dfs(int pos, int sum, int num, int lead, int limit) {
    if (!pos) {
        if (lead && !num) return 1;
        return sum;
    }
    if (!limit && !lead && dp[pos][sum] != -1) return dp[pos][sum];
    int res = 0, up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i ++) {
        int t;
        if (i == num) {
            if (!num) {
                t = sum + (lead == 0);
            } else {
                t = sum + 1;
            }
        } else {
            t = sum;
        }
        res += dfs(pos - 1, t, num, lead && i == 0, limit && i == up);
    }
    return limit ? res : (lead ? res : dp[pos][sum] = res);
}
int cal(int x, int num) {
    memset(dp, -1, sizeof dp);
    len = 0;
    while (x) a[++ len] = x % 10, x /= 10;
    return dfs(len, 0, num, 1, 1);
}
signed main() {
    while (cin >> l >> r, l || r) {
        if (l > r) swap(l, r);
        for (int i = 0; i <= 9; i ++) cout << cal(r, i) - cal(l - 1, i) << " ";
        cout << endl;
    }
}