因为.....因为..... 太久没更新博客了，自己也有点过意不去，于是就.....暑假开始，也没刷题，一天到晚躺在床上，真赤鸡，所以加快更新的脚步，以此激励自己的学习。

      好吧，那什么是数位DP呢？  其实我也不知道，个人理解是对一个数，拆开来进行分析，对于题目的要求写出满足的答案，然后进行DP，也称作 判定性问题的DP，主要用在判定整除、判定可达性上（如存在连续的6666 ，中间的数最大之类的..）其重点是在dp[ i ] [ j ] 上，i是指当前的数是第几位，j 则根据题目要求，不同数值的 j 代表不同的状态，至于状态转移方程，也要根据题目的要求来具体判断。

      在写博客之前，我觉得没必要去写题解，因为题解网上一大堆，自己的代码又难看的要死，后来才发现，如果那样的话，就没必要写博客了-。- （毕竟不是去证明这个理论或者去思考什么大神才去想的高深的东西）。所以，我还是挑几道题目，有个感受吧，对于这个算法。

   
NBUT  [1581]  233333333

    这是一道入门，或者说是模版的题目，意思是在区间L - R 上，有多少数字满足存在23 或者 5 的，比如 324323 ，233333， 5235  那就直接上代码了，不懂的话可以模拟一下，其中：

       dp[ i ] [ 0 ], 表示不存在

　   dp[ i ] [ 1 ], 表示不存在，但最高位为 3

       dp[ i ] [ 2 ], 表示存在

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int dp[10][3];  //  题目的范围是 0 - 1000000000 十位数，所以i = 10 ,取大点也可，分三种状况讨论即可 j = 3

void init()
{
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;  //  为何如此初始化，表示不解，求大神解释一下、
    for(int i = 1; i <= 9; i ++)
    {
        dp[i][0] = dp[i - 1][0] * 9 - dp[i - 1][1];    //  dp[i - 1][0] * 9 表示该位不是5的情况，有九种，减去 这个位置是 3 的 情况 ,下面自己理解。。
        dp[i][1] = dp[i - 1][0];
        dp[i][2] = dp[i - 1][2] * 10 + dp[i - 1][0] + dp[i - 1][1];   
    }
}


int solve(int x)
{
    int digit[15];
    int cnt = 0;
    int tmp = x;
    while(tmp)             //   取出每一位的数
    {
        digit[++cnt] = tmp % 10;
        tmp /= 10;
    }
    digit[cnt + 1] = 0;  // 为了下面的digit[i + 1],i = cnt 的时候
    int flag = 0, ans = 0;              // ans 代表符合题意的数的个数
    for(int i = cnt; i > 0; i --)
    {
        ans += digit[i] * dp[i - 1][2];
        if(flag)    // 当此数满足题意时，比如这个数是 9236
            ans += digit[i] * dp[i - 1][0];   //  所以 923之间满足题意的 ， 再乘以6 就是所有满足题意的数的个数
        else
        {
            if(digit[i] > 5)    //  当你这个位置上的数大于5 的时候，说明你这个数肯定包含了这个位置存在5 的情况， 下面也自己理解...
                ans += dp[i - 1][0];
            if(digit[i] > 2)
                ans += dp[i - 1][1];
            if(digit[i + 1] == 2 && digit[i] > 3)
                ans += dp[i][1];
        }
        if(digit[i] == 5 || digit[i + 1] == 2 && digit[i] == 3)
            flag = 1;
    }
    return ans;
}

int main()
{
    int a, b;
    init();
    while(~scanf("%d%d",&a,&b))
    {
        if(a == 0 && b == 0)
            break;
        printf("%d\n", solve(b + 1) - solve(a));   //  在sovle 函数中，解决没有包括b ,所以要b + 1
    }
}

--------------------------------------------  渣渣的算法路 ， 大神勿喷， 欢迎一起交流 ， 欢迎留言