前置知识: 讲解003、030、031、032、033 - 位运算基础 讲解066、067、068、069 - 动态规划基础 讲解084 - 数位dp-上 【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

数位dp的尝试方式并不特殊，绝大多数都是线性展开，类似从左往右的尝试 之前的课已经讲过 大量在数组上进行线性展开的题目，数位dp是在数字的每一位上进行线性展开而已 不同的题目有不同的限制，解题核心在于：可能性的整理、排列组合的相关知识

解决数位dp的问题 推荐使用记忆化搜索的方式，可能性的展开会很好写，不必刻意追求进一步改写 递归写出来问题就解决了，位数多就挂缓存，位数不多甚至不挂缓存也能通过

数位dp分为上、下节，本节为下期，继续讲解4个题目，来见识更多数位dp问题

题目1 windy数 不含前导零且相邻两个数字之差至少为2的正整数被称为windy数 windy想知道[a,b]范围上总共有多少个windy数 测试链接 : https://www.luogu.com.cn/problem/P2657

题目2 萌数 如果一个数字，存在长度至少为2的回文子串，那么这种数字被称为萌数 比如101、110、111、1234321、45568 求[l,r]范围上，有多少个萌数 由于答案可能很大，所以输出答案对1000000007求余 测试链接 : https://www.luogu.com.cn/problem/P3413

题目3 不含连续1的非负整数 给定一个正整数n，请你统计在[0, n]范围的非负整数中 有多少个整数的二进制表示中不存在连续的1 测试链接 : https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/

题目4 范围内的数字计数 给定两个正整数a和b，求在[a,b]范围上的所有整数中 某个数码d出现了多少次 1 <= a, b 测试链接 : https://leetcode.cn/problems/digit-count-in-range/ 测试链接 : https://www.luogu.com.cn/problem/P2602 测试链接 : https://leetcode.cn/problems/number-of-digit-one/

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com