一、数位dp简介【数位】数位是指把一个数字按照个、十、百、千等一位一位的拆开关注它每一位上的数字。如果拆的是十进制数那么每一个数字是0~9其他进制可以类比十进制。【数位dp解决问题的特点】数位dp求解的问题很固定求某个区间[lr]内满足某个性质的数一共有多少个这个性质一般是针对数位的也就是说和数的组成有关与数的大小无关。并且这类问题的上届很大暴力枚举一定会超时【数位dp的一般思考方式】1、先利用类似前缀和的思想将区间问题 [lr] 转化成 [0r] - [0l-1]2、对于每个区间利用递归枚举每一位要填写的数。二、数位dp模板题问题用递归统计出 0~n 之间一共有多少个数算法原理一位一位地去填数。那么这时候就带来一个问题我们是从最高位开始填还是从最低位开始填比如n 123我们如果从最低位开始个位填到9之后再去填前面两位的话那么可能会填出来129这样的数这时候我们才会发现填的数已经越界了。因此如果我们从最低位开始枚举的话就会枚举出很多非法的数据。所以应该从最高位开始填。在递归过程中我们会发现0_ _形式的数字位数可以从0~9随意填但是1_ _形式的数字十位上就只能填0~2而12_形式的数字个位数又只能填0~3。因此dfs函数的参数应该有两个一个是pos表示要填的数字的位置另一个是bool类型的参数 limit表示是否受限制如果不受限制就从0~9填否则就从0~up填写(up表示上界)。【参考代码-无优化】#include iostream using namespace std; const int N 15; int a[N], n; int dfs(int pos, bool limit) { if (pos 0) return 1; int up (limit ? a[pos] : 9); int ret 0; for (int i 0;i up;i) { ret dfs(pos - 1, limit (i up)); } return ret; } int calc(int x) { while (x) { a[n] x % 10; x / 10; } return dfs(n, true); } int main() { int x 0; cin x; cout calc(x) endl; return 0; }在递归的时候我们发现00_01_02_等等的状态是一样的都是pos 1limit false所以它们返回的值也都是一样的。因此我们可以使用备忘录的方式进行记忆化搜索。【参考代码-优化版】#include iostream using namespace std; const int N 15; int a[N], n; int f[N][2]; // 备忘录 int dfs(int pos, bool limit) { if (pos 0) return 1; if (~f[pos][limit]) // if(f[pos][limit] ! -1) return f[pos][limit]; int up (limit ? a[pos] : 9); int ret 0; for (int i 0;i up;i) { ret dfs(pos - 1, limit (i up)); } return f[pos][limit] ret; } int calc(int x) { // 初始化备忘录 memset(f, -1, sizeof f); while (x) { a[n] x % 10; x / 10; } return dfs(n, true); } int main() { int x 0; cin x; cout calc(x) endl; return 0; }那么能否接着优化呢我们还可以发现limit true的分支只走一次剩下递归的次数全都集中在limit false这个情况下的因此备忘录中只需要记录limit false的结果即可。也就是说 f 数组可以在原来的基础上优化掉第二维。【参考代码-最终版】#include iostream using namespace std; const int N 15; int a[N], n; int f[N]; // 备忘录 int dfs(int pos, bool limit) { if (pos 0) return 1; if (!limit ~f[pos]) return f[pos]; int up (limit ? a[pos] : 9); int ret 0; for (int i 0;i up;i) { ret dfs(pos - 1, limit (i up)); } if (!limit) f[pos] ret; return ret; } int calc(int x) { // 初始化备忘录 memset(f, -1, sizeof f); while (x) { a[n] x % 10; x / 10; } return dfs(n, true); } int main() { int x 0; cin x; cout calc(x) endl; return 0; }三、练习题3.1 数字游戏算法原理和模板有所不同的是当填写pos位置时为了满足题目所说的数的性质我们还需要直到当前所填位置pos的前一个位置prev所填的数。因此dfs函数的参数部分需要加一个参数prev。代码实现#define _CRT_SECURE_NO_WARNINGS 1 #include iostream #include cstring using namespace std; const int N 15; int a[N], n; int f[N][N]; int dfs(int pos, int prev, bool limit) { if (pos 0) return 1; if (!limit f[pos][prev] ! -1) return f[pos][prev]; int up (limit ? a[pos] : 9); int ret 0; for (int i prev;i up;i) { ret dfs(pos - 1, i, limit (i a[pos])); } if (!limit) f[pos][prev] ret; return ret; } int calc(int x) { n 0; memset(f, -1, sizeof f); while (x) { a[n] x % 10; x / 10; } return dfs(n, 0, true); } int main() { int x, y; while (cin x y) { cout calc(y) - calc(x - 1) endl; } return 0; }3.2 windy数算法原理和上一道练习题类似dfs函数的参数肯定是要有posprev和 limit。但是仅仅这样定义的话肯定是不能解决这道题目的。我们在填写pos位置的时候前面的位置可能全都是0而包含前导零的话pos位置所填的数是不会受到题目中限定条件的影响的可以填到0~up。但如果是1250_这样的形式的话pos位置所填的数就又会受到限定条件的影响只能填到2~up。所以dfs参数部分还需要再加一个参数zero。代码实现#include iostream #include cstring using namespace std; const int N 12; int a[N], n; int f[N][N]; int dfs(int pos, int prev, bool limit, bool zero) { if (pos 0) return 1; if (!limit !zero ~f[pos][prev]) return f[pos][prev]; int ret 0; int up (limit ? a[pos] : 9); for (int i 0;i up;i) { if (zero) { ret dfs(pos - 1, i, limit (i a[pos]), zero !i); } else if (abs(i - prev) 2) { ret dfs(pos - 1, i, limit (i a[pos]), zero !i); } } if (!limit !zero) f[pos][prev] ret; return ret; } int calc(int x) { n 0; memset(f, -1, sizeof f); while (x) { a[n] x % 10; x / 10; } return dfs(n, 0, true, true); } int main() { int x, y; cin x y; cout calc(y) - calc(x - 1) endl; return 0; }