前言：数位dp就是换一种穷举方式。额......我第一次看这句话也懵，哎，资深学渣，来记个笔记先。
正常枚举“过渡到”dfs枚举（这里暂时是穷举的数为：1、10、100、1000、10000....，要穷举任意数在后面给出）
其实有些兄弟用了递推关系来做这类题，但个人感觉那种解题方式还是太花时间了。。。。。。。。。。
正常枚举：
#include <iostream> #include <cstdio> #define ll long long using namespace std; int main() { for (int i = 0; i <= 1000) { printf("%d ", i); } return 0; }
结果：略(看数学答案也是这样)
dfs枚举：注意pos参数的意思是枚举到当前数字的位数。dfs是从数字的高位往低位枚举(当数字的枚举是也是从小到大的)。num用于记录当前枚举的数字
dfs(pos=0, num); 表示只枚举长度为1的数字，最大数为9
dfs(pos=1, num); 表示只枚举长度为2的数字，最大数为99
dfs(pos=2, num); 表示只枚举长度为3的数字，最大数为999
最好自己动手测一下其他结果，不要光靠脑袋想，除非...........哈哈
#include <iostream> #include <cstdio> #include <vector> #define ll long long using namespace std; // dfs穷举 void dfs(int pos, vector<int> &num) { if (pos == -1) { // 打印数 for (int i = 0; i < num.size(); i++) printf("%d", num[i]); printf(" "); return; } for (int i = 0; i <= 9; i++) { num.push_back(i);// 添加 dfs(pos-1, num); num.erase(num.end()-1);// 回溯一下 } } int main() { vector<int> num; dfs(2, num); return 0; }
结果显示如下(不完整)：
枚举到任意数：参数limit的引入(其他博主都是取的这个参数名)
正常枚举到任意数：(不用多说)
#include <iostream> #include <cstdio> #include <vector> #define ll long long using namespace std; int main() { for (int i = 0; i <= 任意数; i++) { // ...... } return 0; }
dfs任意数枚举：参数limit的用处，用来控制枚举上界位的数字，为Boolean值，为true的时候，表示当前枚举pos位上的数字有上界，相反则没有。
比如：任意数 = 321，limit初始为true
当枚举到百位上时，3就是百位上的上界，百位就只能取0、1、2、3，而当百位是3时，十位的枚举此时就有了上界2，同理，当百位为3，十位为2，则个位的上界为1。但是当枚举的百位小于3，也就是百位取值为0、1、2时，十位和个位的取值可以是0-9，此时不管怎么取值也不会超出最大值321，因为百位已经是0、1、2开头了，同样个位也是同样的道理。
#include <iostream> #include <cstdio> #include <vector> #define ll long long using namespace std; int a[20];// 保存当前数字各个位上的数字 // dfs穷举 void dfs(int pos, bool limit, vector<int> &num) { if (pos == -1) { // 打印数 for (int i = 0; i < num.size(); i++) printf("%d", num[i]); printf(" "); return; } // 这里的up用来控制最大上界(就是枚举的数不能超过n = 123) int up = limit?a[pos]:9; for (int i = 0; i <= up; i++) { num.push_back(i);// 添加 // limit && i == a[pos] 为true时表示如果当前位有上界，并且枚举到了最大上界值 dfs(pos-1, limit && i == a[pos], num); num.erase(num.end()-1);// 回溯一下，删除刚才添加的数字 } } int main() { vector<int> num; int n = 123; int pos = 0; // 分解数字 while(n > 0) { a[pos++] = n%10; n /= 10; } dfs(pos-1, true, num); return 0; }
结果如下：
。。。。疫情过年好无聊