i数位dp一直以来是dp家族里比较冷门的一种，但一旦考察不会数位dp靠暴力很难骗分。今天我们就来分析一下数位dp的全过程

首先我们要清楚数位dp解决的是什么问题：

求出在给定区间 [A,B] 内，符合条件 f(i) 的数 i 的个数。条件 f(i) 一般与数的大小无关，而与数的组成有关

由于数是按位dp，数的大小对复杂度的影响很小

这里我们使用记忆化搜索实现数位dp。本质上记搜其实就是dp，下文会重点介绍dp值的使用和记录

记搜过程

从起点向下搜索，到最底层得到方案数，一层一层向上返回答案并累加，最后从搜索起点得到最终答案。

对于 [l,r] 区间问题，我们一般把他转化为两次数位dp,即找 [0,r] 和 [0,l-1] 两段，再将结果相减就得到了我们需要的 [l,r]

状态设计

如果理解了上述过程，我们需要考虑的就是怎样判断现在在哪一层，怎样判断当前的状态——这就需要我们传进一些参量。

dfs函数需要哪些参量?

首先是数位dp基本的量数字位数 pos ，记录答案的 st ，最高位限制 limit （这个后面会讲）
我们还需要一个判断判断前导0的标记 lead （这个后面也会讲）
由于数位dp解决的大多是数字组成问题，所以经常要比较当前位和前一位或前几位的关系（根据题意而定），所以一般在dfs()中也要记录前一位或前几位数 pre 方便比较。
除此之外还可以传进更多参量以区分状态，视题意而定。

数位dp的状态能记录的最好都记录上

前导0标记lead

由于我们要搜的数可能很长，所以我们的直接最高位搜起

举个例子：假如我们要从 [0,1000] 找任意相邻两数相等的数

显然 111,222,888 等等是符合题意的数

但是我们发现右端点 1000 是四位数

因此我们搜索的起点是 0000 ，而三位数的记录都是 0111,0222,0888 等等

而这种情况下如果我们直接找相邻位相等则 0000 符合题意而 0111,0222,0888 都不符合题意了

所以我们要加一个前导0标记

如果当前位 lead=1 而且当前位也是0，那么当前位也是前导0， pos+1 继续搜；
如果当前位 lead=1 但当前位不是0，则本位作为当前数的最高位， pos+1 继续搜；（注意这次根据题意st或其他参数可能发生变化）

当然前导 0 有时候是不需要判断的，上述的例子是一个有关数字结构上的性质，0会影响数字的结构，所以必须判断前导0；而如果我们研究的是数字的组成（例如这个数字有多少个 1 之类的问题），0并不影响我们的判断，这样就不需要前导0标记了。总之，这个因题而异，并不是必须要标记（当然记了肯定是不会出错的）

最高位标记limit

我们知道在搜索的数位搜索范围可能发生变化；

举个例子：我们在搜索 [0,555] 的数时，显然最高位搜索范围是 0 ~ 5 ，而后面的位数的取值范围会根据上一位发生变化：

当最高位是 1 ~ 4 时，第二位取值为 [0,9] ;
当最高位是 5 时，第二位取值为 [0,5] （再往上取就超出右端点范围了）

为了分清这两种情况，我们引入了limit 标记：

若当前位 limit=1 而且已经取到了能取到的最高位时，下一位 limit=1 ；
若当前位 limit=1 但是没有取到能取到的最高位时，下一位 limit=0 ；
若当前位 limit=0 时，下一位 limit=0 。

我们设这一位的标记为 limit ，这一位能取到的最大值为 res ，则下一位的标记就是i==res && limit（ i 枚举这一位填的数）

dp值的记录和使用

最后我们考虑dp数组下标记录的值

本文介绍数位dp是在记忆化搜索的框架下进行的，每当找到一种情况我们就可以这种情况记录下来，等到搜到后面遇到相同的情况时直接使用当前记录的值。

dp数组的下标表示的是一种状态，只要当前的状态和之前搜过的某个状态完全一样，我们就可以直接返回原来已经记录下来的dp值。

再举个例子

假如我们找 [0,123456] 中符合某些条件的数

假如当我们搜到 1000??时，dfs从下返上来的数值就是当前位是第 5 位，前一位是 0 时的方案种数，搜完这位会向上反，这是我们可以记录一下：当前位第 5 位，前一位是 0 时，有这么多种方案种数

当我们继续搜到 1010?? 时，我们发现当前状态又是搜到了第 5 位，并且上一位也是 0 ，这与我们之前记录的情况相同，这样我们就可以不继续向下搜，直接把上次的dp值返回就行了。

注意，我们返回的dp值必须和当前处于完全一样的状态，这就是为什么dp数组下标要记录 pos,pre 等参量了。

最重要的来了——

接着上面的例子，范围 [0,123456]

如果我们搜到了 1234??，我们能不能直接返回之前记录的：当前第 5 位，前一位是 4 时的dp值？

答案是否定的

我们发现，这个状态的dp值被记录时，当前位也就是第 5 位的取值是 [0,9] ，而这次当前位的取值是 [0,5] ，方案数一定比之前记录的dp值要小。

当前位的取值范围为什么会和原来不一样呢？

如果你联想到了之前所讲的知识，你会发现：现在的 limit=1 ，最高位有取值的限制。

因此我们可以得到一个结论：当 limit=1 时，不能记录和取用dp值！

类似上述的分析过程，我们也可以得出：当 lead=1 时，也不能记录和取用dp值！

p.s.当然没有这么绝对的说……因题而异的说……

以上就是计划搜索的完整步骤。

附图：

模板

在讲例题之前先讲个基本的动态模板(先看后面的例题也行)：dp思想，枚举到当前位置pos，状态为state(这个就是根据题目来的，可能很多，毕竟dp千变万化)的数量(既然是计数,dp值显然是保存满足条件数的个数)

cpp

typedef long long ll;
int a[20];
ll dp[20][state];//不同题目状态不同
ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零
{
    //递归边界，既然是按位枚举，最低位是0，那么pos==-1说明这个数我枚举完了
    /*这里一般返回1，表示你枚举的这个数是合法的，那么这里就需要你在枚举时必须每一位都要满足题目条件，
    也就是说当前枚举到pos位，一定要保证前面已经枚举的数位是合法的。
    不过具体题目不同或者写法不同的话不一定要返回1 */
    if(pos==-1) return 1;
    //第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
    if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
    /*常规写法都是在没有限制的条件记忆化，这里与下面记录状态是对应，具体为什么是有条件的记忆化后面会讲*/
    int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了
    ll ans=0;
    //开始计数
    for(int i=0;i<=up;i++)//枚举，然后把不同情况的个数加到ans就可以了
    {
        if() ...
        else if()...
        //最后两个变量传参都是这样写的，这里写i=a[pos]也行，因为此时up==a[pos]
        ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==up) 
         
        /*这里还算比较灵活，不过做几个题就觉得这里也是套路了
        大概就是说，我当前数位枚举的数是i，然后根据题目的约束条件分类讨论
        去计算不同情况下的个数，还有要根据state变量来保证i的合法性，比如题目
        要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类，
        前一位如果是6那么这意味就不能是2，这里一定要保存枚举的这个数是合法*/
    }
    //计算完，记录状态
    if(!limit && !lead) dp[pos][state]=ans;
    /*这里对应上面的记忆化，在一定条件下时记录，保证一致性，当然如果约束条件不需要考虑lead，
    这里就是lead就完全不用考虑了*/
    return ans;
}
ll solve(ll x)
{
    int pos=0;
    while(x)//把数位都分解出来
    {
        a[pos++]=x%10;//个人老是喜欢编号为[0,pos),看不惯的就按自己习惯来，反正注意数位边界就行
        x/=10;
    }
    //刚开始最高位都是有限制并且有前导零的，显然比最高位还要高的一位视为0嘛
    return dfs(pos-1/*从最高位开始枚举*/,/*一系列状态 */,true,true);
}
int main()
{
    ll le,ri;
    while(~scanf("%lld%lld",&le,&ri))
    {
        //初始化dp数组为-1,这里还有更加优美的优化,后面讲
        printf("%lld\n",solve(ri)-solve(le-1));
    }
}

例题详解

233. Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example 1:

Input: n = 13
Output: 6

Example 2:

Input: n = 0
Output: 0

Constraints:

\(0 <= n <= 109\)

理解题意

范围 1 ~ n 里所有的整数中出现 1 的个数；如果 n = 12 ，1 到 12 这 12 个数里：

1 贡献了 1 个 1；
10 贡献了 1 个 1；
11 贡献了 2 个 1；
12 贡献了 1 个 1

因此一共 1 + 1 + 2 + 1 = 5 个 1。注意：这里 11 ，「1」出现了两次，所以题目不是问「包含 1」的整数的个数，而是问所有的数里，出现了「1」的总数。

思路分析

这是一道经典的「数位 DP」模板题的简化版，原题在这里。

计数问题，有可能用到「动态规划」。事实上，这道问题就是「动态规划」关于「数位」的入门问题；

「数位」讨论的是（正）整数有关的一些问题。叫「数位」，是把一个数按照个位、十位、百位拆开来看；

因此本题分类讨论（拆分问题）的大致依据是：个位出现 1 的个数、十位出现 1 的个数……，但实际上的分类讨论会稍微复杂一些；

一个基本的拆分方法是：把一个整数拆分成「整块」部分和「余项」部分。

举个例子，例如 2876。

「整块」：2876 是 4 位数，「整块」就是 0~999，不是到 9999，因为 999 是不超过 2879 的最大三位数，0~999 里的 1 的总数是可以直接利用的结果；最高位是 2，说明有 2 个「整块」，分别是「0~999」和「1000~1999」；
「余项」：把最高位去掉，剩下的部分就是「余项」。2876「余项」就是「876」。

定义状态 1（整块部分）

这部分回答的是这样几个问题：

0~9 所有的 1 位数里的 1 的总数；
0~99 所有的 2 位数里的 1 的总数；
……
0~999999 所有的 6 位数里的 1 的总数。

因此定义 A[i] 表示 \(0 \sim 10^{i + 1} - 1\)所有 \(i + 1\) 位数里 1 的总数。

A[0] = 1 这是因为 0~9 所有的 1 位数里的 1 的总数只有 1 。
A[1] 考虑 0~99 所有的 2 位数，分类讨论如下：
个位数固定是 1(A[0] = 1，唯一一种可能，即固定个位为1)，十位数可能是 0、1、2、3、4、5、6、7、8、9 ，一共 10 种可能，因此这种情况下的结果是 10*A[0]；
十位数固定是 1，个位数可能是 0、1、2、3、4、5、6、7、8、9 ，一共 10 种可能，因此这种情况下的结果是 10。
A[2] 考虑 0~999 所有的 3 位数，分类讨论如下：
最高位是 0，剩下是 A[1] ，最高位是 1，剩下是 A[1]，……，最高位是 9，剩下是 A[1]。一共是 10*A[1]；
在上一步，最高位是 1，「最高位」的这个 1 带来的总贡献还没统计出来，因此百位数固定是 1，十位数、个位数是 0~99 一共有 100 个

综上，可以归纳出：

\(A[i] = 10*A[i-1] + 10^i\)

这里 A[i−1]前面的 10指的是最高位是 0、1、…… 、9 的时候，剩下的数位对结果的贡献，所以是乘以 10。
后面 \(10^i\)指的是，最高位是 1 的时候，对结果集的贡献。例如 A[3]，即 0 ~ 9999 里所有的 4 位数对 1 的贡献，1 开头的数一共有 1000 个，它们分别是 1000、10001、…… 、1999，一共\(10^3\)个数字。

定义状态 2（把余项考虑进去）

这部分回答的是这样几个问题，以 2784 为例：

dp[0]表示： 1~4 所有的数里 1 的总数；
dp[1] 表示： 1~84 所有的数里 1 的总数；
dp[2] 表示： 1~784 所有的数里 1 的总数；
dp[3] 表示： 1~2784 所有的数里 1 的总数。

核心的想法是 把「余项」一点一点扩大。

因此 dp[i]表示：1 ~ n 从右向左数 截取到 第i + 1位的所有的数里 1 的总数(因为dp[0]表示截取到第1位)。

所以题目要求的答案是 dp[N - 1]，这里 N 是整数 n 的长度。

因此从右向左遍历时每一位 i（这里 i 从 0 开始），根据看到的数值进行分类讨论，假设当前遍历到的数是 \(d (0 \le d \le 9)\)。

dp[0] ：当 d = 0 时 dp[0] = 0 ，当 d = 1、2、3、4、5、6、7、8、9 时 dp[0] = 1。
如果 d = 0 ，最高位一定不会有 1 ，此时状态值取决于它右边一位的状态值，即 dp[i] = dp[i - 1] ；
如果 d = 1 ，此时分 3 种情况：
- 情况 1：最高位不是 1 ，对当前状态值的贡献是 dp[i - 1]（和 d = 0 的情况一样）
- 情况 2：最高位是 1 ，有多少个数的最高位是 1 呢？看它右边的个数，例如 165，最高位是 1 的元素个数为 66（= 65 + 1），它们是 100、101、…… 、165，
- 情况 3：还有不足 i + 1 位的所有整数里 1 的个数，即刚刚定义的状态 1，答案是 A[i - 1]。
  例如 165，情况 1 是 0~65 里对结果的贡献、情况 2 是 100~165 里对结果的贡献（只数出了最高位的 1 的个数），而 0~99 就是情况 3 对结果的贡献。

所以此时dp[i] = rest（后面有多少个数） + dp[i - 1] + A[i - 1];

如果 d > 1 ，此时分 3 种情况：
- 情况 1：最高位不是 1，对当前状态值的贡献是 dp[i - 1]；
- 情况 2：最高位是 1，对当前状态值的贡献是 \(10^i\)；
- 情况 3：「整块」里对当前状态值的贡献，是 d * A[i - 1]。
  例如 465，情况 1 是 0~65 里对结果的贡献，情况 2 是 100~199 里对结果的贡献（只数出了最高位的 1 的个数），而 0~99 、 100~199（最高位的 1 在「情况 2」已经算过）、 200~299、 300~399 对结果的贡献就是 4 * A[3] 。

所以此时dp[i] = (currChar - '0') * A[i - 1] + dp[i - 1] + (int) Math.pow(10, i);

参考代码

java

public class Solution {

    public int countDigitOne(int n) {
        // 转换成为字符串
        String s = String.valueOf(n);
        char[] charArray = s.toCharArray();
        int len = s.length();
        if (len == 1) {
            return n == 0 ? 0 : 1;
        }
    
        // 第 1 部分：求「整块」的 1 的个数
        // A[i] 表示：0~10^{i+1} - 1 里包含 1 的个数
        // i = 0 时，10^{i+1} - 1 = 10 - 1 = 9
        // i = 1 时，10^{i+1} - 1 = 100 - 1 = 99
        // 5 位数，例如 12345，讨论到 0~9999 里出现的 1 的总数就可以了
        int[] A = new int[len - 1];
        A[0] = 1;
        for (int i = 1; i < len - 1; i++) {
            A[i] = 10 * A[i - 1] + (int) Math.pow(10, i);
        }
    
        // 第 2 部分：求「余项」的 1 的个数
        int[] dp = new int[len];
        if (charArray[len - 1] == '0') {
            dp[0] = 0;
        } else {
            dp[0] = 1;
        }
        for (int i = 1; i < len; i++) {
          	// 从右向左读每一个数位
            char currChar = charArray[len - i - 1];
            if (currChar == '0') {
                // 高位是 0，没有 1，就取决于低位中 1 的个数
                dp[i] = dp[i - 1];
            } else if (currChar == '1') {
                // 最高位是 1，高位是 1 的个数取决于后面有多少个数，要记得加 1
                int rest = Integer.parseInt(s.substring(len - i, len)) + 1;
                // dp[i - 1] 和情况 1 一样理解
                // A[i - 1] 比如 199，A[i - 1] 表示 0 到 99 的里 1 的个数
                dp[i] = rest + dp[i - 1] + A[i - 1];
            } else {
                // 最高位是 2、3、4、5、6、7、8、9、10
                // (currChar - '0') * A[i - 1] 表示有几个整块
                // dp[i - 1] 表示余数部分
                // (int) Math.pow(10, i) 最高位是 1 每一位都是 1 所以是 10 的方幂
                dp[i] = (currChar - '0') * A[i - 1] + dp[i - 1] + (int) Math.pow(10, i);
            }
        }
        return dp[len - 1];
    }

}

复杂度分析

时间复杂度：\(O(\log n)\)，取决于 n 的位数；

空间复杂度：\(O(\log n)\)。

计数类模拟方法求解

由于本题只需求 1 出现的次数，而不需要求解 0 到 9 的出现次数，同时意味着不需要考虑统计 0 次数时的前导零边界问题。

因此，也可以不当作数位 DP 题来做，只当作一道计数类模拟题来求解。

我们可以统计 1 在每一位出现的次数，将其累加起来即是答案。

举个 🌰，对于一个长度为 m 的数字 n，我们可以计算其在「个位（从右起第 1 位）」、「十位（第 2 位）」、「百位（第 3 位）」和「第 m 位」中 1 出现的次数。

假设有 n = abcde，即 m = 5，假设我们需要统计第 3 位中 1 出现的次数，即可统计满足\(--1--\)形式，同时满足\(1 <= --1-- <= abcde\)要求的数有多少个，我们称 \(1 <= --1-- <= abcde\) 关系为「大小要求」。

我们只需对 c 前后出现的值进行分情况讨论：

当 c 前面的部分 \(< ab\)，即范围为 \([0, ab\))，此时必然满足「大小要求」，因此后面的部分可以任意取，即范围为\([0,99]\)。根据「乘法原理」，可得知此时数量为 \(ab * 100\)；
当 c 前面的部分 \(= ab\)，这时候「大小关系」主要取决于 c：
- 当 c = 0，必然不满足「大小要求」，数量为 0；
- 当 c = 1，此时「大小关系」取决于后部分，后面的取值范围为 \([0, de]\)，数量为 \(1 * (de + 1)\)；
- 当 c > 1，必然满足「大小关系」，后面的部分可以任意取，即范围为\([0,99]\)，数量为 \(1 * 100\)；
当 c 前面的部分 > ab，必然不满足「大小要求」，数量为 0。

其他数位的分析同理。

代码：

java

class Solution {
    public int countDigitOne(int n) {
        String s = String.valueOf(n);
        int m = s.length();
        if (m == 1) return n > 0 ? 1 : 0;
        // 计算第 i 位前缀代表的数值，和后缀代表的数值
        // 例如 abcde 则有 ps[2] = ab; ss[2] = de
        int[] ps = new int[m], ss = new int[m];
        ss[0] = Integer.parseInt(s.substring(1));
        for (int i = 1; i < m - 1; i++) {
            ps[i] = Integer.parseInt(s.substring(0, i));
            ss[i] = Integer.parseInt(s.substring(i + 1));
        }
        ps[m - 1] = Integer.parseInt(s.substring(0, m - 1));
        // 分情况讨论
        int ans = 0;
        for (int i = 0; i < m; i++) {
            // x 为当前位数值，len 为当前位后面长度为多少
            int x = s.charAt(i) - '0', len = m - i - 1;
            int prefix = ps[i], suffix = ss[i];
            int tot = 0;
            tot += prefix * Math.pow(10, len);
            if (x == 0) {
            } else if (x == 1) {
                tot += suffix + 1;
            } else {
                tot += Math.pow(10, len);
            }
            ans += tot;
        }
        return ans;
    }
}

c++版本

cpp

class Solution {
public:
int countDigitOne(int n) {
    vector<int> bits;
    int m = n;
    while(m>0){
        bits.emplace_back(m%10);
        m/=10;
    }
    //此时bits是n各个位倒过来的
    int ans = 0;
    if(bits.size()==1) return n>0?1:0;
    for(int i=0;i<bits.size();++i){
        int prefix = i==bits.size()-1?0:n/(int)pow(10,i+1);
        int suffix = i==0?0:n%(int)pow(10,i);
        ans += prefix*pow(10,i);
        if(bits[i]==1){
            ans += suffix+1;
        }else if(bits[i]>1){
            ans+=pow(10,i);
        }
    }
    return ans;
}
};

java

class Solution {
    int string2int(string s){
        stringstream ss;
        ss<<s;
        int i;
        ss>>i;
        return i;
    }
public:
    int countDigitOne(int n) {
        string s = to_string(n);
        int m = s.size();
        if(m==1) return n>=1?1:0;
        //考虑每一位为1的情况
        //假设有 n = abcde
        int ans = 0;
        for(int i=0;i<m;++i){
            int x = s[i] - '0';
            int prefix = i==0? 0 : string2int(s.substr(0, i));
            int suffix = i==m-1? 0 : string2int(s.substr(i+1,m-i-1));
            // c 前面的部分 < ab的贡献
            ans += prefix * pow(10,m-i-1);
            //c 前面的部分 = ab的贡献
            if(x==1){
                ans += suffix+1;
            }else if(x>1){
                ans += pow(10,m-i-1);
            }
            //c 前面的部分 > ab的贡献为0
        }
        return ans;
    }
};

题目推荐

[HDU2089]不要62

入门题，如果上面的例题没看懂可以先尝试一下这道题，如果上面的例题理解了这题可以秒切

P2657 [SCOI2009]windy数
P2602 [ZJOI2010]数字计数

这两题是数位dp题目里的基础题，多体会上述的讲解就能够顺利地想出解法（实在不行还可以背板子的吧）

P3413 萌数

这道题是笔者接触数位dp的第一题，当时学长讲完之后还有点懵，现在发现不是特别难的题目，还是比较套路的

P4127 [AHOI2009]同类分布
P4317 花神的数论题

相比前面，这道题就显得灵活一些，可能在统计答案的方法上有一些变化，但相信当你做完上面的题之后，这两道题也不在话下！

HDU 2089 不要62

入门题。就是数位上不能有4也不能有连续的62，没有4的话在枚举的时候判断一下，不枚举4就可以保证状态合法了，所以这个约束没有记忆化的必要，而对于62的话，涉及到两位，当前一位是6或者不是6这两种不同情况我计数是不相同的，所以要用状态来记录不同的方案数。

dp[pos][sta]表示当前第pos位，前一位是否是6的状态，这里sta只需要去0和1两种状态就可以了，不是6的情况可视为同种，不会影响计数。

cpp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
int a[20];
int dp[20][2];
int dfs(int pos,int pre,int sta,bool limit)
{
    if(pos==-1) return 1;
    if(!limit && dp[pos][sta]!=-1) return dp[pos][sta];
    int up=limit ? a[pos] : 9;
    int tmp=0;
    for(int i=0;i<=up;i++)
    {
        if(pre==6 && i==2)continue;
        if(i==4) continue;//都是保证枚举合法性
        tmp+=dfs(pos-1,i,i==6,limit && i==a[pos]);
    }
    if(!limit) dp[pos][sta]=tmp;
    return tmp;
}
int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,-1,0,true);
}
int main()
{
    int le,ri;
    //memset(dp,-1,sizeof dp);可优化
    while(~scanf("%d%d",&le,&ri) && le+ri)
    {
        memset(dp,-1,sizeof dp);
        printf("%d\n",solve(ri)-solve(le-1));
    }
    return 0;
}

常用优化吧：

memset(dp,-1,sizeof dp);放在多组数据外面。

这一点是一个数位特点，使用的条件是：约束条件是每个数自身的属性，而与输入无关。
具体的：上一题不要62和4，这个约束对每一个数都是确定的，就是说任意一个数满不满足这个约束都是确定，比如444这个数，它不满足约束条件，不管你输入的区间是多少你都无法改变这个数不满足约束这个事实，这就是数自身的属性（我们每组数据只是在区间计数而已，只能说你输入的区间不包含444的话，我们就不把它统计在内，而无法改变任何事实）。
由此，我们保存的状态就可以一直用(注意还有要limit，不同区间是会影响数位在有限制条件下的上限的)
这点优化就不给具体题目了，这个还有进一步的扩展。不过说几个我遇到的简单的约束： 1. 求数位和是10的倍数的个数,这里简化为数位sum%10这个状态，即dp[pos][sum]这里10 是与多组无关的，所以可以memset优化，不过注意如果题目的模是输入的话那就不能这样了。 2. 求二进制1的数量与0的数量相等的个数，这个也是数自身的属性。 3. 。。。。。

把不满足前提的通过修改，然后优化。

介绍之前,先说一种较为笨拙的修改，那就是增加状态，前面讲limit的地方说增加一维dp[pos][state][limit]，能把不同情况下状态分别记录(不过这个不能memset放外面)。
基于这个思想，我们考虑：约束为数位是p的倍数的个数，其中p数输入的，这和上面sum%10类似，但是dp[pos][sum]显然已经不行了，每次p可能都不一样，为了强行把memset提到外面加状态dp[pos][sum][p]，对于每个不同p分别保存对应的状态。这里前提就比较简单了，你dp数组必须合法，p太大就G_G了。所以对于与输入有关的约束都可以强行增加状态(这并不代表能ac，如果题目数据少的话就随便你乱搞了)

HDU 4734 相减。

题目给了个f(x)的定义：\(F(x)=F(x)=A_n\ast 2^{n-1}+A_{n-1}\ast 2^{n-2}+...+A_2\ast 2+A_1\ast 1\)，\(A_i\)是十进制数位，然后给出a,b求区间[0,b]内满足f(i)<=f(a)的i的个数。

常规想：这个f(x)计算就和数位计算是一样的，就是加了权值，所以dp[pos][sum]，这状态是基本的。a是题目给定的，f(a)是变化的不过f(a)最大好像是4600的样子。如果要memset优化就要加一维存f(a)的不同取值，那就是dp[10][4600][4600]，这显然不合法。

这个时候就要用减法了：dp[pos][sum]表示的是枚举到当前pos位，后面还需要凑sum的权值和的个数，

也就是说初始的是时候sum是f(a),枚举一位就减去这一位在计算f(i)的权值，那么最后枚举完所有位 sum>=0时就是满足的，后面的位数凑足sum位就可以了。

仔细想想这个状态是与f(a)无关的(新手似乎很难理解)，一个状态只有在sum>=0时才满足，如果我们按常规的思想求f(i)的话，那么最后sum>=f(a)才是满足的条件。

cpp

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
 
using namespace std;
const int N=1e4+5;
int dp[12][N];
int f(int x)
{
    if(x==0) return 0;
    int ans=f(x/10);
    return ans*2+(x%10);
}
int all;
int a[12];
int dfs(int pos,int sum,bool limit)
{
    if(pos==-1) {return sum<=all;}
    if(sum>all) return 0;
    if(!limit && dp[pos][all-sum]!=-1) return dp[pos][all-sum];
    int up=limit ? a[pos] : 9;
    int ans=0;
    for(int i=0;i<=up;i++)
    {
        ans+=dfs(pos-1,sum+i*(1<<pos),limit && i==a[pos]);
    }
    if(!limit) dp[pos][all-sum]=ans;
    return ans;
}
int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,true);
}
int main()
{
    int a,ri;
    int T_T;
    int kase=1;
    scanf("%d",&T_T);
    memset(dp,-1,sizeof dp);
    while(T_T--)
    {
        scanf("%d%d",&a,&ri);
        all=f(a);
        printf("Case #%d: %d\n",kase++,solve(ri));
    }
    return 0;
}

POJ 3252 Round Numbers

这题的约束就是一个数的二进制中0的数量要不能少于1的数量，通过上一题，这题状态就很简单了，dp[pos][num],到当前数位pos,0的数量减去1的数量不少于num的方案数，一个简单的问题，中间某个pos位上num可能为负数(这不一定是非法的，因为我还没枚举完嘛，只要最终的num>=0才能判合法，中途某个pos就不一定了)，这里比较好处理，Hash嘛，最小就-32吧(好像),直接加上32，把32当0用。这题主要是要想讲一下lead的用法，显然我要统计0的数量，前导零是有影响的。至于!lead&&!limit才能dp，都是类似的，自己慢慢体会吧。

cpp

#pragma comment(linker, "/STACK:10240000,10240000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<map>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
const double R=0.5772156649015328606065120900;
const int N=1e5+5;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
int dp[35][66];
int a[66];
int dfs(int pos,int sta,bool lead,bool limit)
{
    if(pos==-1)
        return sta>=32;
    if(!limit && !lead && dp[pos][sta]!=-1) return dp[pos][sta];
    int up=limit?a[pos]:1;
    int ans=0;
    for(int i=0;i<=up;i++)
    {
        if(lead && i==0) ans+=dfs(pos-1,sta,lead,limit && i==a[pos]);//有前导零就不统计在内
        else ans+=dfs(pos-1,sta+(i==0?1:-1),lead && i==0,limit && i==a[pos]);
    }
    if(!limit && !lead ) dp[pos][sta]=ans;
    return ans;
}
int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x&1;
        x>>=1;
    }
    return dfs(pos-1,32,true,true);
}
int main()
{
    memset(dp,-1,sizeof dp);
    int a,b;
    while(~scanf("%d%d",&a,&b))
    {
        printf("%d\n",solve(b)-solve(a-1));
    }
    return 0;
}

HDU 4507 新的领域--计数转求和

这题麻烦就是要求数的平方和。

我们先考虑求和的问题，一个区间，数位dp能在一些约束下计数，现在要这些数的和。其实组合数学搞搞就可以了：

如现在枚举的某一位pos,我统计了这一位枚举i的满足条件的个数cnt，其实只要算i对总和的贡献就可以了，对于一个数而言第pos位是i，那么对求和贡献就是i*10^pos,就是十进制的权值，然后有cnt个数都满足第pos位是i，最后sum=cnt*i*10^pos.原理就是这样平方和可以看做(a*10^pos+b)^2,a是你当前pos位要枚举的，b其实是个子问题，就是pos之后的位的贡献值，把这个平方展开就可以了！

cpp

#pragma comment(linker, "/STACK:10240000,10240000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<map>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
const double R=0.5772156649015328606065120900;
const int N=1e5+5;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
ll fact[20];
void init()
{
    fact[0]=1;
    for(int i=1;i<20;i++)
        fact[i]=fact[i-1]*10%mod;
}
struct node
{
    ll cnt,sum,sqr;
    node(ll cnt=-1,ll sum=0,ll sqr=0):cnt(cnt),sum(sum),sqr(sqr){}
}dp[20][7][7];
int a[20];
ll fac(ll x)
{
    return x*x%mod;
}
ll dfs(int pos,ll num,ll val,ll&cnt,ll&sum,bool limit)
{
    if(pos==-1) {
        if(num==0 || val==0)
            return 0;
        cnt=1;
        return 0;
    }
    if(!limit && dp[pos][num][val].cnt!=-1) {
            cnt=dp[pos][num][val].cnt;
            sum=dp[pos][num][val].sum;
            return dp[pos][num][val].sqr;
    }
    int up=limit?a[pos]:9;
    ll sq=0;
    for(int i=0;i<=up;i++)
    if(i!=7)
    {
        ll cn=0,su=0;
        ll tmp=dfs(pos-1,(num+i)%7,(val*10+i)%7,cn,su,limit && i==a[pos]);
        ll tm=i*fact[pos]%mod;
        tmp=(tmp+fac(tm)*cn%mod+(tm*su%mod)*2%mod)%mod;//计数之后要更新sum,sqr
        sum=(sum+su+(i*fact[pos]%mod)*cn%mod)%mod;
        cnt=(cnt+cn)%mod;
        sq=(sq+tmp)%mod;
    }
    if(!limit) dp[pos][num][val]=node(cnt,sum,sq);
    return sq;
}
ll solve(ll x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    ll t1=0,t2=0;
    return dfs(pos-1,0,0,t1,t2,true);
}
bool judge(ll x)
{
    int sum=0;
    int pos=0;
    if(x%7==0) return false;
    while(x)
    {
        if(x%10==7) return false;
        sum+=x%10;
        x/=10;
    }
    sum%=7;
    return sum!=0;
}
int main()
{
    init();
    for(int i=0;i<20;i++)
        for(int j=0;j<7;j++)
        for(int k=0;k<7;k++)//memset
    {
        dp[i][j][k].cnt=-1;
        dp[i][j][k].sum=0;
        dp[i][j][k].sqr=0;
    }
    int T_T;
    scanf("%d",&T_T);
    while(T_T--)
    {
        ll le,ri;
        scanf("%I64d%I64d",&le,&ri);
        ll ans=solve(ri)-solve(le-1);
        ans=(ans%mod+mod)%mod;
        printf("%I64d\n",ans);
    }
    return 0;
}

当然也有些题看起来不是数位dp，但是可能依靠一些数论知识把问题转化成一道数位dp题（比如一些数字本身的性质转化成数字组成的特点），这里就不再过多赘述。

二叉树

AVL Tree

Red Black Tree

B Tree

Interval Trees

加权图最短路径

背包问题

子序列问题

二维图

记搜过程

状态设计

前导0标记lead

最高位标记limit

dp值的记录和使用

模板

例题详解

理解题意

思路分析

定义状态 1（整块部分）

定义状态 2（把余项考虑进去）

参考代码

复杂度分析

计数类模拟方法求解

题目推荐

HDU 2089 不要62

HDU 4734 相减。

POJ 3252 Round Numbers

HDU 4507 新的领域--计数转求和

记搜过程 ​

状态设计 ​

前导0标记lead ​

最高位标记limit ​

dp值的记录和使用 ​

模板 ​

例题详解 ​

理解题意 ​

思路分析 ​

定义状态 1（整块部分） ​

定义状态 2（把余项考虑进去） ​

参考代码 ​

复杂度分析 ​

计数类模拟方法求解 ​

题目推荐 ​

HDU 2089 不要62 ​

HDU 4734 相减。 ​

POJ 3252 Round Numbers ​

HDU 4507 新的领域--计数转求和 ​

记搜过程

状态设计

前导0标记lead

最高位标记limit

dp值的记录和使用

模板

例题详解

理解题意

思路分析

定义状态 1（整块部分）

定义状态 2（把余项考虑进去）

参考代码

复杂度分析

计数类模拟方法求解

题目推荐

HDU 2089 不要62

HDU 4734 相减。

POJ 3252 Round Numbers

HDU 4507 新的领域--计数转求和