数据结构与算法：数位dp

前言

最近感觉有点flop，写不大动题了……总有各种各样的事儿占用本就不多的补题时间……

一、数位dp

1.内容

数位dp就是在数字的每一位上展开可能性。

2.方法

因为位数不大，所以一般数位dp的题写出记忆化搜索即可。

3.核心

核心就是可能性的展开和一些排列组合的知识。

二、题目

1.统计各位数字都不同的数字个数

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n==0)
        {
            return 1;
        } 
        if(n==1)
        {
            return 10;
        }

        //一位：0~9十种情况
        //两位：9*9种情况
        //三位：9*9*8种情况
        //     …………

        int ans=10;
        int bit=9;
        for(int i=2,k=9;i<=n;i++,k--)
        {
            bit*=k;
            ans+=bit;
        }

        return ans;
    }
};

这个题就是个排列组合问题。最高位有1～9九种情况，下一位0～9且和上一位不同，也是九种情况。之后0～9且和前两位不同，八种情况，以此类推。

2.最大为 N 的数字组合

class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& strs, int num) {
        
        //计算offset -> 方便提取数字
        int tmp=num/10; 
        int len=1;
        int offset=1;
        while(tmp>0)
        {
            tmp/=10;
            len++;
            offset*=10;
        }

        //重构strs数组
        vector<int>digits;
        for(string str:strs)
        {
            digits.push_back(str[0]-'0');
        }

        //打表：已知前缀比num小，剩下i位有几种排列
        vector<int>cnts(len);
        cnts[0]=1;
        int ans=0;//位数不够的情况
        for(int i=digits.size(),j=1;j<len;j++,i*=digits.size())
        {
            cnts[j]=i;
            ans+=i;
        }

        //return recursion(0,0,len,digits,num,offset);
        return ans+op(len,digits,cnts,num,offset);
    }

    //剩下len位没决定，前缀是否比num小free，之前用没用过数字fix
    int recursion(int free,int fix,int len,vector<int>&digits,int num,int offset)
    {
        if(len==0)
        {
            return fix==1?1:0;
        }

        int ans=0;
        int cur=(num/offset)%10;//提取当前位数字
        
        //之前没选过数字
        if(fix==0)
        {
            ans+=recursion(1,0,len-1,digits,num,offset/10);//不选
        }

        //前缀和num一样
        if(free==0)
        {
            for(int i:digits)
            {
                if(i<cur)
                {
                    ans+=recursion(1,1,len-1,digits,num,offset/10);
                }
                else if(i==cur)
                {
                    ans+=recursion(0,1,len-1,digits,num,offset/10);
                }
                else
                {
                    break;//有序数组digits
                }
            }
        }
        else//前缀小于num -> 随便选
        {
            ans+=digits.size()*recursion(1,1,len-1,digits,num,offset/10);//任意选
        }

        return ans;
    }

    int op(int len,vector<int>&digits,vector<int>&cnts,int num,int offset)
    {
        if(len==0)
        {
            return 1;
        }

        int ans=0;
        int cur=(num/offset)%10;

        for(int i:digits)
        {
            if(i<cur)
            {
                ans+=cnts[len-1];//小于直接从表里拿
            }
            else if(i==cur)
            {
                ans+=op(len-1,digits,cnts,num,offset/10);
            }
            else
            {
                break;
            }
        }

        return ans;
    }
};

这个题就正式进入数位dp的范围了。

因为要求小于num，所以考虑从十进制高位开始，这样便于判断大小关系。之后，若当前位上选的数字小于num，则后续不管怎么选都必小于num，所以设置free变量判断是否可以自由选。然后，因为从最高位开始，所以不一定每个位都必须有数，也可以前若干位空着不选，从中间某位开始再选，所以要再带一个fix变量，表示之前是否选过数字。这三个变量在数位dp问题里的非常常见。

之后，若len为0，即来到最后了，若此时fix为1，表示之前选过数字，所以找到了一种；若为0，表示之前一个数都没选过，那就不能算一种情况。之后，因为每步都要提取出当前位的数，所以还要带着offset递归，方便每一步取数，这也是数位dp的重要技巧。

然后，若之前没选过数，那么到当前位仍然可以不选。若前缀和num一样，即当前不能自由选，那就遍历每个digits表里的数字，若小于当前位cur，那就可以选，此时后续就可以自由选；若等于cur，也可以选，但后续同样不能自由选；而因为digits有序，所以当大于cur时直接break即可。而当可以自由选时，那直接就是digits的大小乘以后续自由选的情况数即可。

观察可以发现，当可以自由选时，后续的情况数其实可以直接计算出来。那就可以先打一张表，表示前缀比num小，剩下j位的情况数。其中，可以先统计出当位数不够len，即有位置不选的情况下的情况数ans，之后只需要求位数必然为len的情况数。此时就只需要带着len一个参数递归，对于每个位置都遍历digits表，若小于cur就直接从表里拿，等于的话再去调递归。

3.统计整数数目