动态规划——数位dp入门（二）

对数字整体进行考虑的处理方法

较为简单的数位dp只会涉及到每一位上的数字变化，如比较相邻数字差，是否含有某个数字等等，在这种情况下一般用dp【i】【j】就可以，i表示数字长度，j用来表示首位数字。如果题目要求对数字整体进行考虑，我们不能对各个位置上的数直接判断，就需要对每位之前判断过的数进行记忆化存储。

题目hdu3652 number

http://acm.hdu.edu.cn/showproblem.php?pid=3652

题意是让你求范围内出现１３且能被１３整除的数的个数。

<span style="font-size:14px;">#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;

int num[15],len,maxlen;
int dp[20][13][3];
//dp[i][j][k]表示i位数，对13的余数是j
//k为0表示没有出现13
//k为1表示没有出现13，但是首位为3
//k为2表示出现13

int dfs(int len,int first,int mod,bool flag,bool ok)// len长度，first第一个数，mod取的模，flag到达上个位置的最大值，ok已经有13
{
    if(len <= 0)
        return ok&&(mod==0);  //如果已经出现了13，而且余数为0，返回1，否则为0

    if(!flag &&  ok && dp[len][mod][0]!=-1)
        return  dp[len][mod][0];  //已经出现13且前一位不是最大值，那么后面就可以直接取长度

    if(!flag && !ok && dp[len][mod][2]!=-1 && first!=1)
        return dp[len][mod][2];

    if(!flag && !ok && dp[len][mod][1]!=-1 && first==1)
        return dp[len][mod][1];  //之前没有13，但是末位是1，那么后面的高位可以是3

    int over;
    if(!flag) // 如果没取到这个位置的最大值，则下一位可取到9
        over = 9;
    else
        over = num[len];

    int sum = 0;
    for(int i = 0; i <= over; i++){//对下个位置的值进行遍历
        int yushu = (mod*10+i)%13;//对每次取的数进行记忆化，在下次dfs中使用而不影响回溯
        sum += dfs(len-1,i,yushu,flag&&(i==over),ok||(first==1&&i==3));
    }

    if(!flag)
    {
        if(first==1 && !ok) dp[len][mod][1] = sum;
        if(first!=1 && !ok) dp[len][mod][2] = sum;
        if(ok) dp[len][mod][0] = sum;
    }
    return sum;
}

int shudp(int number)
{
    len = 0;
    while(number > 0)
    {
        num[++len] = number%10;
        number /= 10;
    }
    maxlen = len;
    return dfs(len,0,0,true,false);
}

int main()
{
    int number;
    memset(dp,-1,sizeof(dp));
    while(scanf("%d",&number)!=EOF)
        printf("%d\n",shudp(number));
    return 0;
}</span>
           

由这个例题可以得出一个解这种涉及到数据本身的数位ｄｐ的基本步奏：

（１）．在shudp()函数中将该数分解存储。

（２）．由dfs()函数进行主要求解。

其中dfs()函数中，会读取每次的len(数字长度)来进行在数位上的遍历(如万，千，百．．．)最后停止dfs()。还会有一个对该数位数值是否到达最大的bool型(即该例题中的flag),一个对针对题意的限制条件(即该例题中的 ok ).

将这个dfs过程可以细分为几个区域：

这一块是在dfs()过程中对sum的累加。

　if(len <= 0)
        return ok&&(mod==0);  //如果已经出现了13，而且余数为0，返回1，否则为0

    if(!flag &&  ok && dp[len][mod][0]!=-1)
        return  dp[len][mod][0];  //已经出现13且前一位不是最大值，那么后面就可以直接取长度

    if(!flag && !ok && dp[len][mod][2]!=-1 && first!=1)
        return dp[len][mod][2];

    if(!flag && !ok && dp[len][mod][1]!=-1 && first==1)
        return dp[len][mod][1];  //之前没有13，但是末位是1，那么后面的高位可以是3
           

　int over;
    if(!flag) // 如果没取到这个位置的最大值，则下一位可取到9
        over = 9;
    else
        over = num[len];
           

这一块是算出下一位能达到的值的最大值。

　int sum = 0;
    for(int i = 0; i <= over; i++){//对下个位置的值进行遍历
        int yushu = (mod*10+i)%13;//对每次取的数进行记忆化，在下次dfs中使用而不影响回溯
        sum += dfs(len-1,i,yushu,flag&&(i==over),ok||(first==1&&i==3));
    }
           

这一块是dfs()的递归部分，每一次的dfs()都在这里暂停，进入下一次的dfs()中，直至结束。

　if(!flag)
    {
        if(first==1 && !ok) dp[len][mod][1] = sum;
        if(first!=1 && !ok) dp[len][mod][2] = sum;
        if(ok) dp[len][mod][0] = sum;
    }
    return sum;
           

这一块dfs()进行到最后，开始对dp数组处理，return之后开始回溯，不停的return，直至到最开始的dfs。