数据结构学习 数位dp

关键词：数位dp 记忆化搜索 dfs

数位dp属于比较难的题目，所有数位dp在leetcode都是hard。

因为没有做出jz43.里面用到了数位dp，所以去学习了一下，学习看了这位大神的基础知识。

题目基本上是跟着这位灵大哥的题单做的。

学完数位dp之后，我发现数位dp是一个非常套路化的过程，难点是确定dp需要记忆的内容。要结合实际例子来理解这个套路化的过程。

数位dp的套路：

关键思想：

从高到低给每位数填数字。

比如：要填四位数，从xxxx开始，填了2xxx，再填23xx。

需要两个循环：

第一个循环（是一个递归，调用dfs函数，每次pose+1）：遍历每一位数字，给每一位填数字。（第一位2xxx，第二位21xx，这样的）

第二个循环：遍历每一位数字的可选项，每一种可选项都填一遍。（要填第一位，可以填1，2，3，4，5...）

islimit：

可选项的确定依靠这个bool，表示这一位的数字是否收到上限的限制。如果这一位数没受到限制，我们就可以填0-9（十进制）或者0-1（二进制）。如果受到限制，那么就只能填这一位数的上限。

如果确定这一位数是否收到限制：如果它的前一位不受限制，那么这一位一定不受限制。如果它的前一位受到限制，那么得看我们前一位填的是否等于前一位数的上限，如果等于，那么这一位依然受到限制。

比如：我们只能从2345-0000这一段填数字，我们从高到低填数字。（初始化默认islimit==true，因为前几位填的数字都是000，和上限一样。）

假如目前状态是xxxx，第一位受到限制，只能填2-0。

????????1、填了2，2xxx，那么第二位继续受到限制只能填3-0，我们不可能填24xx 25xx 26xx这些了，大了。

? ? ? ? 2、填了1，1xxx，那么第二维就自由了，它填0-9都可以，不论是19xx还是10xx都不会超过2345.

数位dp的函数参数：

数位dp里的dfs的函数一般需要一下这些参数，不一定是所有参数都被需要：

?

题目一：面试题 17.06. 2出现的次数?

?

思路：

逐位填写数字，每一位枚举要填入的数字。对于本题来说，由于前导零对答案无影响，isNum可以省略。

dp状态：

dp[pose][count]：构造到从左往右第pose位，已经出现了 count个2，在这种情况下，继续构造最终会得到的2的个数。初始化为-1。

中止条件：

if(pose<0) return count;//中止条件

说明这一条已经填完了，返回的是这一路的数字二的个数，比如1222，返回3；1221，返回2

调取记忆：

if(!islimit&&dp[pose][count]>=0) return dp[pose][count];

//注意只有在islimit==0而且之前有记载过的时候才可以调取。

求上限：

int up=islimit?dig[pose]:9;

求上限，即求可选值。如果有上限，那么取上限值。

开始填数，temp计录每一位可选值的结果：

? ? ? ? int temp=0;//用来计数，记录在这个状态下，继续填数，一共可以得到的2的个数
? ? ? ? for(int i=0;i<=up;++i)
? ? ? ? {
? ? ? ? ? ? temp=temp+fun(pose-1,islimit&&i==dig[pose],count+(i==2),dp);
? ? ? ? }

i<=up//这一位填的数不能超过up

pose-1//填下一位数

islimit&&i==dig[pose]//是否有限制的确定

count+(i==2)//如果这一位填的数为2，计数+1

画了个示意图，方便理解temp记的是啥，返回的又是啥。

?
?

记忆化：

注意前提是没有限制。

? ? ? ? if(!islimit)//记忆化
? ? ? ? ? ? dp[pose][count]=temp;

复杂度计算：

时间复杂度O(log^2 n)

时间复杂度 = 状态个数 * 单个状态的转移次数，状态个数就是 dp 数组的长度，即 O(log^2 n) ，而单个状态的转移次数 = O(10) = O(1)，所以时间复杂度为 O(log^2 n)

空间复杂度O(log^2 n)?

代码：

class Solution {
public:
    int fun(int pose,bool islimit,int count,vector<vector<int>>& dp)
    {
        if(pose<0) return count;//中止条件
        if(!islimit&&dp[pose][count]>=0) return dp[pose][count];//记忆化
        int up=islimit?dig[pose]:9;//求上限
        int temp=0;//用来计数
        for(int i=0;i<=up;++i)
        {
            temp=temp+fun(pose-1,islimit&&i==dig[pose],count+(i==2),dp);
        }
        if(!islimit)//记忆化
            dp[pose][count]=temp;
        return temp;
    }
    int numberOf2sInRange(int n) {
        while(n)//把数分成一位一位
        {
            dig.push_back(n%10);
            n=n/10;
        }
        vector<vector<int>> dp(dig.size(),vector<int>(dig.size()+1,-1));//dp状态，初始化为-1
        return fun(dig.size()-1,true,0,dp);//dfs
    }
    vector<int> dig;
};

?题目二：不含连续1的非负整数

这道题我是看了答案才会的。

?

思路：

逐位填写数字，每一位枚举要填入的数字。对于本题来说，由于前导零对答案无影响，isNum可以省略。

?dp状态：

std::vector<vector<int>> dp(dig+1,vector<int>(2,-1));

dp[pose][pre]：第pose-1位为pre时，构造从左往右第pose位及其之后数位的合法方案数

中止条件：

if(pose<0) return 1;//中止条件

说明这一条已经填完了，返回的是1，表示这一路的已经被统计了，比如10101（二进制），返回1；10100（二进制），又返回1

?调取记忆：

if (!islimit && dp[pose][pre] >= 0) return dp[pose][pre];//之前已经记录了

注意这里要!islimit

求上限：

int up = islimit ? (n >> pose)&1 : 1;

开始填数，temp计录每一位可选值（合法组合数）的结果：

这里只能填0或者0和1。要看上限是0还是1。

        //temp 统计合法的组合数
        int temp = fun(pose - 1, 0, islimit && up==0, n, dp);//如果下一个数字填0
        if(up==1&&pre==0) temp+=fun(pose-1,1,islimit&&up==1,n,dp);//如果下一个数字填1：前提是前一个数字不能为1而且可以填1

记忆化：

if (!islimit) dp[pose][pre] = temp;//记忆化

复杂度计算：

时间复杂度O(logn) //2*logn

空间复杂度O(logn) //存dp

代码：

class Solution {
public:
    int findIntegers(int n) {
        int dig = 0;
        int temp = n;
        while (temp)
        {
            dig++;
            temp = temp >> 1;
        }
        std::vector<vector<int>> dp(dig+1,vector<int>(2,-1));
        return fun(dig - 1, 0, true, n, dp);
    }
    int fun(int pose, int pre, bool islimit, int n, std::vector<std::vector<int>>& dp)
    {
        //dp状态：第pose-1位为pre时，构造从左往右第pose位及其之后数位的合法方案数
        if (pose < 0) return 1;//中止条件
        if (!islimit && dp[pose][pre] >= 0) return dp[pose][pre];//之前已经记录了
        int up = islimit ? (n >> pose)&1 : 1;
        //temp 统计合法的组合数
        int temp = fun(pose - 1, 0, islimit && up==0, n, dp);//如果下一个数字填0
        if(up==1&&pre==0) temp+=fun(pose-1,1,islimit&&up==1,n,dp);//如果下一个数字填1：前提是前一个数字不能为1而且可以填1
        if (!islimit) dp[pose][pre] = temp;//记忆化
        return temp;
    }
};

?题目三：这位灵大哥的题单

?[ 用时: 23 m 30 s ] 自己写出来了

?

思路：

逐位填数字，可以填digits的数字，也可以填0（前导零），为了区分前导零和其他数字，所以需要hasnum（isnum）来控制前导零。

dp状态：

题解是没有记录hasnum状态的，我记录了。

dp[pose][hasnum]：在hasnum的状态下，构造从左往右第pose位及其之后数位的合法方案数

vector<vector<int>> dp(dig.size(),vector<int>(2,-1));

中止条件：

if(pose<0) return 1;

hasnum状态：

? ? ? ? //hasnum==1：前面有非零的数字

? ? ? ? //hasnum==0：前面全是零（前导零）?

?比如n=9999，那么就是有四个空可以填数字。我们可以只填一位：1，也可以填两位：13，也可以填三位：135，还可以填四位：1351。

如果前面不填，比如只填了两位：0013，那么前面的0就是前导零。

注意：hasnum的状态会影响到dp，所以我们才要把dp状态里面加入hasnum状态。

? ? ? ? //比如：n=1000，当pose=1，也就是我们第一个数已经填了

? ? ? ? //第一个数填了digits里的数（比如7），即hasnum==1时，现在的填数状态：7???，那么第二位就不能填0了

? ? ? ? //第一个数填了0（前导零），即hasnum==0时，现在的填数状态：0???，那么第二位既可以填digits也可以填0

调取记忆：

if(!islimit&&dp[pose][hasnum]>=0) return dp[pose][hasnum];//之前记录了

求上限：

int up=islimit?dig[pose]:9;//上限

开始填数，temp计录每一位可选值（合法组合数）的结果：

可以填两种数，一种是digits里的数，一种是前导零。

        for(int i=0;i<=up;++i)
        {
            if(digits_hash.find(i)!=digits_hash.end())//填digits里面的数
            {
                temp+=fun(pose-1,true,islimit&&i==up,digits_hash,dig,dp);//填了所以hasnum==true
            }
            if(i==0&&hasnum==false&&pose!=0)//如果&hasnum==false，就可以继续填0
            {//pose!=0是为了防止00000全零也被算进去的情况：如果到了pose==0的时候，前面还是全零，最后一个数就不能继续填0了
                temp+=fun(pose-1,false,islimit&&i==up,digits_hash,dig,dp);//继续填0所以hasnum==false
            }
        }

记忆化：

if(!islimit) dp[pose][hasnum]=temp;//记忆化

复杂度计算：

时间复杂度O(logn)

空间复杂度O(logn)

代码：

class Solution {
    //填数字，可以填digits的数字，也可以填0（前导零）
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        vector<int> dig;//把n逐位拆分
        while(n)
        {
            dig.push_back(n%10);
            n=n/10;
        }
        unordered_map<int,int> digits_hash;//把digits转为字典
        for(const string&s:digits)
        {
            digits_hash[s[0]-'0']=1;
        }
        //dp状态：在hasnum的状态下，构造从左往右第pose位及其之后数位的合法方案数
        //hasnum==1：前面有非零的数字
        //hasnum==0：前面全是零（前导零）
        //hasnum的状态会影响到dp。
        //比如：n=1000，当pose=1，也就是我们第一个数已经填了
        //第一个数填了digits里的数（比如7），即hasnum==1时，现在的填数状态：7???，那么第二位就不能填0了
        //第一个数填了0（前导零），即hasnum==0时，现在的填数状态：0???，那么第二位既可以填digits也可以填0
        vector<vector<int>> dp(dig.size(),vector<int>(2,-1));
        return fun(dig.size()-1,false,true,digits_hash,dig,dp);
    }
    int fun(int pose,bool hasnum,bool islimit,const unordered_map<int,int>& digits_hash,const vector<int>& dig,vector<vector<int>>& dp)
    {
        if(pose<0) return 1;
        if(!islimit&&dp[pose][hasnum]>=0) return dp[pose][hasnum];//之前记录了
        int up=islimit?dig[pose]:9;//上限
        int temp=0;//记录该阶段（该pose）的合法数
        for(int i=0;i<=up;++i)
        {
            if(digits_hash.find(i)!=digits_hash.end())//填digits里面的数
            {
                temp+=fun(pose-1,true,islimit&&i==up,digits_hash,dig,dp);//填了所以hasnum==true
            }
            if(i==0&&hasnum==false&&pose!=0)//如果&hasnum==false，就可以继续填0
            {//pose!=0是为了防止00000全零也被算进去的情况：如果到了pose==0的时候，前面还是全零，最后一个数就不能继续填0了
                temp+=fun(pose-1,false,islimit&&i==up,digits_hash,dig,dp);//继续填0所以hasnum==false
            }
        }
        if(!islimit) dp[pose][hasnum]=temp;//记忆化
        return temp;
    }
};

题目四：至少有 1 位重复的数字

看了答案才会的 主要是把求重复变成求非重复这里没想到，而且vis用int来表示我没想到。

思路：

? ? //关键思想：求有重复了太困难了，求不重复的比较简单

? ? //先求不重复的，然后总数-不重复的=重复的

? ? //所以：逐位填入不重复的数字

? ? //注意这题需要isnum来控制前导零的

dp状态：

vector<vector<int>> dp(dig.size(),vector<int>(1<<10,-1));

dp[pose][vis]在前面已经被用了vis的情况下，构造第pose位及其之后数位的合法方案数

为什么第二维是1<<10呢？请看vis状态。

vis状态：

vis记录了前面选过的数字。

注意：这里有一个技巧，这里的vis不是一个长度为10的vector，而是int，节省空间了。

• 问：那么怎么记录呢？
• 答：比如vis=(00000000101)(2进制)即(5)(10进制)，意味着0和2被用过了
• 问：为什么dp第二维是1<<10呢？
• 答：在构造dp的时候，为了装下vis=(0000000000)~(1111111111)(2进制)，所以要用(10000000000)(2进制)的大小，所以大小写成1<<10

?isnum状态：

前面是否填了除了前导零以外的数字。这个状态可以记可以不记，上一题我记了，这一题我没记是因为如果记就三维了，太多了。

中止条件：

表示这一分支已经填数字填到底了，完成了1组数字组合，返回1

if(pose<0) return 1;

调取记忆：

if(!islimit&&dp[pose][vis]>=0) return dp[pose][vis];

求上限：

int up=islimit?dig[pose]:9;

开始填数，temp计录每一位可选值（合法组合数）的结果：

这里分成两种情况，前面全是0和前面有非零的数字：

? ? ? ? 1、如果前面全为0，即if(!isnum)

? ? ? ? ? ? ? ? a、那么如果继续填零，isnum的状态不变（注意：pose不能在==0的时候再填0了，不然整个数字全是0）

? ? ? ? ? ? ? ? b、如果填了别的数，isnum的状态改变

? ? ? ? 2、如果前面有非零的数字

? ? ? ? ? ? ? ? a、?这个数之前没有被用过(vis>>i &1)==0，那么统计

? ? ? ? ? ? ? ? b、?这个数之前被用过(vis>>i &1)!=0，那么跳过

        for(int i=0;i<=up;++i)
        {//这里分成两种情况，前面全是0和前面有非零的数字
            if(!isnum)//如果前面全是0
            {
                if(i==0&&pose!=0)//填0：前面全是0，那么再加一个0，isnum还是保持不变，相当于啥都没做。pose不能在==0的时候再填0了，不然整个数字全是0
                {//所以vis不记录，这时候vis=(0000000000)
                    temp+=fun(pose-1,vis,islimit&&i==up,isnum,dig,dp);
                }//填除了0其他的
                else if(i!=0)
                {//vis|(1<<i)：比如填了个2，那么1<<i：(100)(2进制) 按位或（其实这里用+也没事）：将1<<i合并进vis里面
                //isnum要改成true，因为填数了
                    temp+=fun(pose-1,vis|(1<<i),islimit&&i==up,true,dig,dp);
                }  
            }
            else if((vis>>i &1)==0)//如果前面有非零数字，那么只需要判断这个数之前有没有被用过(vis>>i &1)==0
            {//同上
                temp+=fun(pose-1,vis|(1<<i),islimit&&i==up,true,dig,dp);
            }
        }

?记忆化：

注意：要在没有任何限制的情况下（!islimit&&isnum）才记忆化

if(!islimit&&isnum) dp[pose][vis]=temp;//记忆化

复杂度计算：

代码：

class Solution {
    //关键思想：求有重复了太困难了，求不重复的比较简单
    //先求不重复的，然后总数-不重复的=重复的
    //所以：逐位填入不重复的数字
    //注意这题需要isnum来控制前导零的
public:
    int numDupDigitsAtMostN(int n) {
        int m=n;
        vector<int> dig;
        while(n)
        {
            dig.push_back(n%10);
            n=n/10;
        }//把n逐位分成一个一个数字
        //dp状态：在前面已经被用了vis的情况下，构造第pose位及其之后数位的合法方案数
        //vis记录了前面选过的数字
        //注意这里有一个技巧，这里的vis不是一个长度为10的vector，而是int，那么怎么记录呢？
        //比如vis=(00000000101)(2进制)即(5)(10进制)，意味着0和2被用过了
        //在构造dp的时候，为了装下vis=(0000000000)~(1111111111)(2进制)，所以要用(10000000000)(2进制)的大小，所以大小写成1<<10
        vector<vector<int>> dp(dig.size(),vector<int>(1<<10,-1));
        return m-fun(dig.size()-1,0,true,false,dig,dp);
    }
    int fun(int pose,int vis,bool islimit,bool isnum,const vector<int>& dig,vector<vector<int>>& dp)
    {
        if(pose<0) return 1;//中止条件，表示这一分支已经填数字填到底了，完成了1组数字组合，返回1
        if(!islimit&&dp[pose][vis]>=0) return dp[pose][vis];//之前已经记录过了
        int up=islimit?dig[pose]:9;
        int temp=0;
        for(int i=0;i<=up;++i)
        {//这里分成两种情况，前面全是0和前面有非零的数字
            if(!isnum)//如果前面全是0
            {
                if(i==0&&pose!=0)//填0：前面全是0，那么再加一个0，isnum还是保持不变，相当于啥都没做。pose不能在==0的时候再填0了，不然整个数字全是0
                {//所以vis不记录，这时候vis=(0000000000)
                    temp+=fun(pose-1,vis,islimit&&i==up,isnum,dig,dp);
                }//填除了0其他的
                else if(i!=0)
                {//vis|(1<<i)：比如填了个2，那么1<<i：(100)(2进制) 按位或（其实这里用+也没事）：将1<<i合并进vis里面
                //isnum要改成true，因为填数了
                    temp+=fun(pose-1,vis|(1<<i),islimit&&i==up,true,dig,dp);
                }  
            }
            else if((vis>>i &1)==0)//如果前面有非零数字，那么只需要判断这个数之前有没有被用过(vis>>i &1)==0
            {//同上
                temp+=fun(pose-1,vis|(1<<i),islimit&&i==up,true,dig,dp);
            }
        }
        if(!islimit&&isnum) dp[pose][vis]=temp;//记忆化
        return temp;
    }
};