数位dp浅析

(以下内容默认读者基本了解了dp的基本知识)

数位dp是主要用于解决计数问题的dp,由于其解题模式较为单一,且相关问题容易看出解决方法(指看起来时间复杂度爆表的计数可考虑用数位dp),所以推荐给大家。


  • 首先,我们先考虑用数位dp解决一个不需要用数位dp解决的问题,即在 (0,x] 的范围内有多少个整数。显而易见,答案就是有 x 个整数。

方便起见,我们举的第一个例子中x的值为9999。

我们首先可以得到这样一个公式: dp[pos][i]=dp[pos][i]+dp[pos-1][j],(0 \leq i,j \leq 9) ,其中 pos 代表 x 的第几位,比如 pos=0 时,代表在x的个位。则 dp[pos][i] 的意思就是,在数的 pos 位取 i 这个值时,小于 pos 位的数位的值可以在范围内任意变化,求有多少种任意变化的组合。如当 dp[1][4]=1010 种组合分别是: 40,41,42,43,44,45,46,47,48,49

然后,我们将 dp[0][i] 的初始值都设为 1 ,这样的话就按照上述的递推公式就能得到所有 dp[数位长度-1][i] 的值,而它们的和就是我们要求的 x 内的数的个数。 (就是有x个数!)

点击查看相关代码
    for(int pos=0;pos<len;pos++)
    {
        for(int i=0;i<10;i++)
        {
            if(pos==0)
            {
                dp[pos][i]=1;
                continue;
            }
            for(int j=0;j<10;j++)
            {
                dp[pos][i]+=dp[pos-1][j];
            }
        }
    }
    int ans=0;
    for(int i=0;i<10;i++)
    {
        ans+=dp[len-1][i];
    }

这里的len的值取的就是例子中9999的数位长度——4。


  • 接下来我们取第二个例子,这时的数不再是 9999 ,而是 3758 。此时我们不能再用上述的递推公式了,因为位数上有了限制,对于高位来说,低位的 0-9 的数不一定能取全了。

这时该怎么算呢?我们考虑一下这种对于位数的限制是怎么来的。可以发现,对于位数的值的限制都是由更高一位的位数决定的。如对于对于 3758 来说,当千位是 0,1,2 时,百位的数值是可以在 [0,9] 之间任取的,而当千位是 3 时,百位的取值范围就只能是 [0,7] 了。这样的话,低位的值受高位的影响。
那么我们就可以将递推公式变为从高位到低位,然后得到一个粗糙的递推公式(这个公式是有错误的): dp[pos][i]+=dp[pos+1][j],(0 \leq j \leq str[pos+1],0 \leq i \leq (j==str[pos+1])?str[pos]:9)
此外,还需要一个limit变量来表示高位是否在受限状态。如果不在受限状态,那高位的取值就不用受约束了。即千位为0,1,2时,百位就不在受限状态了。所以最终的递推公式如下(这个就正确了):

dp[pos][i][t]+=dp[pos+1][j][limit],(t=(limit&&i==str[pos]),0<=j<=limit?str[pos+1]:9,0<=i<=limit?str[pos]:9)
点击查看相关代码
    for(int pos=len-1;pos>=0;pos--)
    {
        for(int i=0;i<10;i++)
        {
            if(pos==len-1)
            {
                if(i<cx[pos])dp[pos][i][0]=1;
                else if(i==cx[pos])dp[pos][i][1]=1;

                continue;
            }
            for(int limit=0; limit<2; limit++)
            {
                if(limit&&i>cx[pos])continue;
                int top=limit?cx[pos+1]:9;
                for(int j=0; j<=top; j++)
                {
                  
                    int t=limit&&i==cx[pos];
                    dp[pos][i][t]+=dp[pos+1][j][limit];
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<10;i++)
    {
        ans+=dp[0][i][0];
        ans+=dp[0][i][1];
    }

cx是存储数的int数组


运行了上述代码后会发现一个问题,即输出的结果是相比于正解总是多 1 。是什么地方出了问题呢?实际上,上述的递推公式多算了一种情况,即全为 0 的情况。为了避免这种情况,我们可设一个 prez 变量,来代表是否有前导 0 ,具体的实现和上面加上limit这个维度的类似。当然,也可以不用这种处理方式,比如在上述两个例子中,直接将答案 -1 就能得到正确答案了。究竟要不要加相关的变量,要根据具体的情况决定。

  • 显而易见,如果使用加维度这种操作,具体的实现可能会很麻烦,所以可以采用dfs的形式而非for循环的形式,对于考虑limit的情况,代码实现如下:
点击查看相关代码
int dfs(char str[],int pos,int dig,int limit)
{
    if(pos==0)return 1;
    if(!limit&&dp[pos][dig]!=0)return dp[pos][dig];
    int top=limit?str[pos-1]:9;
    int ans=0;
    for(int i=0;i<=top;i++)
    {
        ans+=dfs(str,pos-1,i,limit&&i==top);
    }
    if(!limit)dp[pos][dig]=ans;
    return ans;
}

你可能会问了,我用数位dp就为了求一个数的值是多少,有意义吗?我不能直接看出来吗? 意义就在于数位dp求数的值不是一个一个数,其时间复杂度主要和数位和进制有关。此外,数位dp能将数位和数的部分状态存储起来,可以在其中做条件的判定。 总的来说,数位dp适合求大数范围内符合条件的计数问题。


既然学习了数位dp的基础知识,不如就尝试下做下相关习题吧,以下题目按照个人理解的难度从易到难排列,将会在1周后左右时间放出个人的题目解答。

HDU-2089

POJ-2282

CodeForces-914C

UVA-11361

CodeForces-55D

3赞
粤 ICP 备 2020080455 号