本期笔记的内容为数位DP

相关链接：

1.往期笔记： 查看
2.来源：yxc老师的算法提高课

【提高版】DP知识笔记7 $\quad$ 有猷 编

update：2020年4月3日 21:43:32 —— 增加了 例题3 ：恨7不成妻 的代码

思路模板：

例题：

1. 度的数量

思路：见【思路模板】

$C++代码：$ https://www.acwing.com/activity/content/code/content/254075/
（为了使内容尽量短小，方便大家查阅，从本篇笔记开始，代码用链接方式分享给大家）

2. Windy数

注意点：

• 本题需要特判前导零
• 最高位不能为零
• 特判第1~n-1位数

思路：
1.树形结构图思路：

2.动态规划思路：

3.恨7不成妻

思路：

f[i][j][k][l] 表示 i 位数字，最高位填j， 和 mod 7 = k, 每一位数和 mod 7 = l 的状态
s0 表示数量， s1 表示数值和， s2 表示平方和
引用一下 墨染空 大佬的解释：

int u = f[i][j][k][l], v = f[i - 1][u][mod(k - j, 7)][mod(l - j, 7)]
u.s0 += v.s0;
u.s1 += v.s1 + j * v.s0 * PowP[i - 1];
u.s2 += v.s2 + (j * PowP[i - 1]) ^ 2 + 2 * j * v.s1;

推荐练习：

• AcWing 1082. 数字游戏
• AcWing 1084. 数字游戏II
• AcWing 1085. 不要62