更好的阅读体验

数位dp模板(dfs)

typedef long long ll

int k[n.length];    //n的10/2进制上界数组
ll f[n.length];    //记忆化数组
ll dfs(int pos,int lead,int limit){//当前位pos 当前位是否是前导0 之前位是否都取到上界
    if(!pos){return 1;}    //枚举完了一条分支
    //当limit和lead不影响记忆化时 返回之前记忆化数组存储的个数。
    if(!limit&&!lead&&f[pos]!=-1)return f[pos];
    //根据之前位limit情况,确定当前位上界
    int up=limit?k[pos]:9;
    int res=0;
    for(int i=0;i<=up;++i){
        if(){}
        else if(){}
        // 向下一位转移。
        dfs+=dfs(pos-1,limit&&i==up,lead&&i==0);
    }
    //当limit和lead不会影响记忆化,记忆化存储当前至记忆化数组
    if(!limit&&!lead)f[pos]=res;
    return res;
}
ll dp(int x){//获取n的上界数组
    int pos=0;
    while(x){
        k[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,true,true);//limit和lead均初始化为true
}
int cntnums(int n) {
    memset(f,-1,sizeof f);//记忆化数组需要初始化
    return f(n);
}

acwing 338 计数问题

给定两个整数 a 和 b，求 a 和 b 之间的所有数字中0~9的出现次数。

例如，a=1024，b=1032，则 a 和 b 之间共有9个数如下：

1024 1025 1026 1027 1028 1029 1030 1031 1032

其中‘0’出现10次，‘1’出现10次，‘2’出现7次，‘3’出现3次等等…

输入格式
输入包含多组测试数据。

每组测试数据占一行，包含两个整数 a 和 b。

当读入一行为0 0时，表示输入终止，且该行不作处理。

输出格式
每组数据输出一个结果，每个结果占一行。

每个结果包含十个用空格隔开的数字，第一个数字表示‘0’出现的次数，第二个数字表示‘1’出现的次数，以此类推。

数据范围

• 0<a,b<100000000

输入样例：

1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0

输出样例：

1 2 1 1 1 1 1 1 1 1
85 185 185 185 190 96 96 96 95 93
40 40 40 93 136 82 40 40 40 40
115 666 215 215 214 205 205 154 105 106
16 113 19 20 114 20 20 19 19 16
107 105 100 101 101 197 200 200 200 200
413 1133 503 503 503 502 502 417 402 412
196 512 186 104 87 93 97 97 142 196
398 1375 398 398 405 499 499 495 488 471
294 1256 296 296 296 296 287 286 286 247

思路

对于数$0~9$分别从最高位$cnt$向最低位$0$递归,

对到第$i$位,

1 维护到第$i$位是否能取最大值$limit$,

2 及从第$cnt$位到第i位是否全为$0$(全为$0$的情况是无效的)

3 到底$cnt$位有$sum$个$x$了

4 up = limit==true?k[idx]:9

• 记忆化递归原理分析

  假设当前是记录1的个数,且当前位不是前导零,当前位没有最高位up限制,则分支
  101 _ _与110 _ _再往下继续开分支开的都是一样的,所以只要走过一次101 _ _,就能存住$f[3][2]$。

$dfs(idx,x,sum,lead,limit)$
$for \quad i\quad in (0,9):$

$dfs(idx-1,x,sum+(lead|i)and(i==x),lead|i,limit\quad and\quad (i==up))$

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
const int N=2001;
ll k[N],f[N][N];
// f[dep][sum] 第dep位 sum
ll dfs(int dep,int x,ll sum,bool lead,bool limit)
{
    // dep==0 
    if(!dep)return sum;
    // lead!=0没有前导零 !limit当前位没有受限
    if(lead&&!limit&&(f[dep][sum]!=-1)) return f[dep][sum];
    // 受限了的话上限=k的dep位,没受限的话上限=9
    int up = limit?k[dep]:9;
    ll res = 0;
    for(int i=0;i<=up;i++)
    {
        res+=dfs(dep-1,x,sum+((lead|i) && (i==x)),lead|i,limit&&(i==up));// 如果i和前面一直都是0,lead|0后还是0
    }
    if(lead&&!limit)f[dep][sum]=res;
    // 因为lead时包含当前位i的数是否是0的 即如果lead==0 此时到第i位全都是0 即0000 则!lead=true 所以不能算一个数
    return res;
}

ll dp(ll n,int x)
{
    int cnt=0;
    while(n) k[++cnt]=n%10,n/=10;
    return dfs(cnt,x,0,false,true);//从最高位开始
}

int main()
{
    ll a,b;
    while(cin >> a >> b,a)
    {
        if(a>b)swap(a,b);
        for(int i=0;i<10;i++)
        {
            memset(f,-1,sizeof f);
            cout << dp(b,i)-dp(a-1,i) << ' ';
        }
        cout << endl;
    }
    return 0;
}

leetcode 233 数字1的个数

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例:

示例:

输入: 13
输出: 6 
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。

思路

• 状态表示
  $f[pos][sum]$:第$pos$位,从最高位到$pos$位$1$的个数为$sum$的总共的数的个数
• 状态转移

typedef long long ll;
class Solution {
public:
    int k[11];
    ll f[11][2000];
    int countDigitOne(int n) {
        memset(f,-1,sizeof f);
        int cnt=0;
        while(n)
        {
            k[++cnt]=n%10;
            n/=10;
        }
        return dfs(cnt,0,true,true);
    }
    ll dfs(int pos,ll sum,bool lead,bool limit)
    {
        if(!pos)return sum;
        if(!lead&&!limit&&f[pos][sum]!=-1)return f[pos][sum];
        ll res = 0;
        int up = limit?k[pos]:9;
        for(int i=0;i<=up;i++)
        {
            res+=dfs(pos-1,sum+(i==1),lead&&(i==0),limit&&(i==up));
        } 
        if(!lead&&!limit)f[pos][sum]=res;
        return res;
    }
};

• 状态表示
  $f[pos]$代表$[0,10\hat{ }pos)$中$1$的个数

  $\sum_{x \in\left[n \cdot 10^{i},(n+1) \cdot 10^{i}\right)} f(x)=10^{i} \cdot f(n)+\sum_{x \in\left[0,10^{i}\right)} f(x)$

  所以如果加了前导零约束会导致不满位的数记忆化且没有提前return ,但实际上是要记忆化return的

typedef long long ll;
class Solution {
    #define maxn 11
public:
    int k[maxn];
    ll f[maxn],pw[maxn]={1};
    int countDigitOne(int n) {
        for(int i=1;i<maxn;i++)pw[i]=pw[i-1]*10;
        memset(f,-1,sizeof f);
        int cnt=0;
        while(n)
        {
            k[++cnt]=n%10;
            n/=10;
        }
        return dfs(cnt,0,true,true);
    }
    ll dfs(int pos,int sum,bool lead,bool limit)
    {
        if(!pos)return sum;
        if(!limit&&f[pos]!=-1)return f[pos]+sum*pw[pos];
        ll res = 0;
        int up = limit?k[pos]:9;
        for(int i=0;i<=up;i++)
        {
            res+=dfs(pos-1,sum+(i==1),lead&&(i==0),limit&&(i==up));
        } 
        if(!limit)f[pos]=res;
        return res;
    }
};

leetcode 357 计算各个位数不同的数字个数-二进制状态表示

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。

示例:

输入: 2
输出: 91 
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。

思路

• 状态表示
  $f[pos][state]$

$state$二进制数维护一个数$i$用没用过的状态

typedef long long ll;
class Solution {
private:
    int k[20]={0};
    long long f[20][1<<11];
public:
    int countNumbersWithUniqueDigits(int n) {
        ll x=1;
        memset(f,-1,sizeof f);
        while(n)
        {
            x*=10;
            n--;
        }
        int cnt=0;
        x=x-1;//左闭右开
        while(x)
        {
            k[++cnt]=x%10;
            x/=10;
        }
        return dfs(cnt,0,true,true);
    }
    int dfs(int pos,int state,bool lead,bool limit)
    {
        if(!pos)return 1;
        if(f[pos][state]!=-1)return f[pos][state];
        int up=limit?k[pos]:9;
        ll res=0;
        for(int i=0;i<=up;i++)
        {
            if(lead&&i==0)res+=dfs(pos-1,state,true,limit&&(i==up));
            else
            {
                if(state&(1<<i))continue;
                else res+=dfs(pos-1,state|(1<<i),lead&&(i==0),limit&&(i==up));
            }
        }
        f[pos][state]=res;
        return res;
    }
};

leetcode 600不含连续1的非负整数

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。

示例 :

输入: 5
输出: 5
解释: 
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

数据范围

• 说明: 1 <= n <= 10^9

思路

• 状态表示$f[pos][pre]$

• 状态转移$f[pos][pre] + =f[pos-1][cur] 如果pre和cur不同时为1$

typedef long long ll;
class Solution {
public:
    int k[31];
    ll f[31][2];
    int findIntegers(int num) {
        memset(f,-1,sizeof f);
        int cnt=0;
        while(num)
        {
            k[++cnt]=num%2;
            num>>=1;
        }
        //当前位选的cur进到下一位的dfs就成了下一位dfs的前一位了 所以初始化pre=0
        return dfs(cnt,0,true);
    }
    ll dfs(int pos,int pre,bool limit)
    {
        if(!pos)return 1;//右子树的最右
        if(!limit && f[pos][pre]!=-1)return f[pos][pre];
        int up=limit?k[pos]:1;
        ll res =0;
        for(int cur=0;cur<=up;cur++)
        {
            if(pre&&cur==1)continue;//前一位和当前位
            res+=dfs(pos-1,cur,limit&&(cur==up));//当前位选的cur进到下一位的dfs就成了下一位dfs的前一位了 所以
        }
        if(!limit)f[pos][pre]=res;
        return res;
    }
};

leetcode 902 最大为N的数字组合

我们有一组排序的数字 D，它是 {'1','2','3','4','5','6','7','8','9'} 的非空子集。（请注意，'0' 不包括在内。）

现在，我们用这些数字进行组合写数字，想用多少次就用多少次。例如 D = {'1','3','5'}，我们可以写出像 '13', '551', '1351315' 这样的数字。

返回可以用 D 中的数字写出的小于或等于 N 的正整数的数目。

示例：

输入：D = ["1","3","5","7"], N = 100
输出：20
解释：
可写出的 20 个数字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

数据范围

• D 是按排序顺序的数字 ‘1’-‘9’ 的子集。
• 1 <= N <= 10^9

思路

class Solution {
private:
    vector<int> f;
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        string s = to_string(n);
        vector<int> vec;
        for(auto &c:digits)
        {
            vec.push_back(stoi(c));
        }
        f = vector<int>(s.size()+1,-1);
        return dfs(vec,s,0,0,false,true);
    }

    int dfs(vector<int> &vec,string s,int cnt,int num,bool lead,bool limit)
    {
        if(cnt == s.size())
        {
            if(num)return 1;
            else return 0;
        }
        if(!limit && !lead && f[s.size()-cnt]!=-1)
        {
            return f[s.size()-cnt];// 没有前导零 且不是右子树
        }
        int ret=0;
        int up = limit?s[cnt]-'0':9;//如果前面没有取最大,则当前随意取,否则当前值最大只能取到s[cnt]
        // num不等于0时
        for(auto i:vec)
        {
            if(i>up)break;
            ret+=dfs(vec,s,cnt+1,num+1,false,i==up && limit);
        }
        if(num==0)ret+=dfs(vec,s,cnt+1,num,true,false);
        if(!limit && !lead)f[s.size()-cnt]=ret;//没前导零 当前位没取最大,取了最大时则要到最右子树才共同作为一种情况
        return ret;
    }
};

leetcode 1012 至少有一位重复的数字

给定正整数 N，返回小于等于 N 且具有至少 1 位重复数字的正整数的个数。

示例：

输入：20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。

数据范围

• 1 <= N <= 10^9

思路

$leetcode357$各个位数不同数个数 的逆问题

$res =n+1-ans(lc357)$

• 状态表示
  $f[pos][state]$位置在$pos$ 状态为$state$的方案数
• 状态转移

  1. 含前导零

     $dfs(pos-1,state,true,limit \quad and \quad (i==up)$
     2. 不含前导零

     $f[pos][state] +=f[pos-1][state|(1<<i)] 如果state中不包含i$

typedef long long ll;
class Solution {
public:
    int k[10];
    ll f[10][1<<11];
    int numDupDigitsAtMostN(int N) {
        int cnt=0;
        memset(f,-1,sizeof f);
        int n=N;
        while(N)
        {
            k[++cnt]=N%10;
            N/=10;
        }
        return n+1-dfs(cnt,0,true,true);
    }
    ll dfs(int pos,int state,bool lead,bool limit)
    {
        if(!pos)return 1;
        if(!lead && !limit && f[pos][state]!=-1)return f[pos][state];
        int up = limit?k[pos]:9;
        ll res = 0;
        for(int i=0;i<=up;i++)
        {
            if(lead&&i==0)res+=dfs(pos-1,state,true,limit&&i==up);
            else
            {
                if((state>>i)&1)continue;
                res+=dfs(pos-1,state|(1<<i),lead&&(i==0),limit&&(i==up));
            }

        }
        if(!lead &&!limit)f[pos][state]=res;
        return res;
    }
};

leetcode 1067 范围内的数字计数-包含0的情况分类讨论

给定一个在 0 到 9 之间的整数 d，和两个正整数 low 和 high 分别作为上下界。返回 d在 low 和 high 之间的整数中出现的次数，包括边界 low 和 high。

示例：

输入：d = 1, low = 1, high = 13
输出：6
解释： 
数字 d=1 在 1,10,11,12,13 中出现 6 次。注意 d=1 在数字 11 中出现两次。

数据范围：

• 0 <= d <= 9
• 1 <= low <= high <= 2×10^8

思路

• 状态表示
  $f[pos][sum]$:$[cnt\sim pos]$位中有$d$的数为$sum$的数中$d$的个数

• 状态转移
  对于$d==0$的情况需要分开讨论

  1. 如果到了$pos$不是前导$0$或者是最后一位,res+=dfs(pos-1,sum+1,lead,limit)
  2. 如果到了$pos$仍是前导$0$,该位的$0$不算,res+=dfs(pos-1,sum,lead,limit)

  其他情况res+=dfs(pos-1,d,sum+(i==d),lead&&(i==0),limit&&(i==up))

typedef long long ll;
class Solution {
    #define maxn 11
public:
    int f[maxn][2000],k[maxn];
    int digitsCount(int d, int low, int high) {
        return dp(high,d)-dp(low-1,d);
    }
    ll dp(int x,int d)
    {
        memset(f,-1,sizeof f);
        int cnt=0;
        while(x)
        {
            k[++cnt]=x%10;
            x/=10;
        }
        return dfs(cnt,d,0,true,true);
    }
    ll dfs(int pos,int d,ll sum,bool lead,bool limit)
    {
        if(!pos)return sum;
        if(!lead && !limit && f[pos][sum]!=-1)return f[pos][sum];
        ll res = 0;
        int up = limit?k[pos]:9;
        for(int i=0;i<=up;i++)
        {
            if(d==0)
            {//如果d是0 则到pos不是前导0 或者 pos是最小的位置上是0 则可以计一位
                if((!lead||pos==0)&&i==0)res+=dfs(pos-1,d,sum+1,lead&&(i==0),limit&&(i==up));
                //如果d是0 则到i仍然是前导0的话就依然还是sum
                else res+=dfs(pos-1,d,sum,lead&&(i==0),limit&&(i==up));
            }
            else
            {
                res+=dfs(pos-1,d,sum+(i==d),lead&&(i==0),limit&&(i==up));
            }
        }
        if(!lead&&!limit)f[pos][sum]=res;
        return res;
    }
};

leetcode 248 中心对称数Ⅲ

中心对称数是指一个数字在旋转了180 度之后看起来依旧相同的数字（或者上下颠倒地看）。

写一个函数来计算范围在 [low, high] 之间中心对称数的个数。

示例:

输入: low = "50", high = "100"
输出: 3 
解释: 69，88 和 96 是三个在该范围内的中心对称数

数据范围:

由于范围可能很大，所以 low 和 high 都用字符串表示。

思路

此题不用数位dp,只是为后面一道题做铺垫,方法是bfs

class Solution {
public:
    char dl[5]={'1','8','0','9','6'};
    char dr[5]={'1','8','0','6','9'};
    bool larger(string& a,string& b)
    {
        if(a.size()!=b.size())return a.size()>b.size();
        return a>=b;
    }
    bool check(string& cur,string& low,string& high)
    {
        return larger(cur,low)&&larger(high,cur);
    }
    int strobogrammaticInRange(string low, string high) {
        queue<string> q;
        string strs[5] = {"","0","1","8"};
        for(auto str:strs)
        {
            q.push(str);
        }
        int res = 0;
        unordered_map<string,int> dic;
        while(q.size())
        {
            string cur = q.front();
            q.pop();
            if(cur.size()>=low.size() && cur.size()<=high.size())
            {
                if(!(cur[0]=='0' && cur.size()>1))
                {
                    if(check(cur,low,high) && !dic.count(cur))
                    {
                        dic[cur]=1;
                        res++;
                    }                    
                }
            }
            if(cur.size()>high.size())continue;// 只要比high小 我就可以在两边加
            for(int i=0;i<5;i++)
            {
                string ne = dl[i]+cur+dr[i];
                if(ne.size()>high.size())continue;
                q.push(ne);
            }
        }
        return res;
    }  
};

leetcode 1088 易混淆数Ⅱ

本题我们会将数字旋转 180° 来生成一个新的数字。

比如 0、1、6、8、9 旋转 180° 以后，我们得到的新数字分别为 0、1、9、8、6。

2、3、4、5、7 旋转 180° 后，是 无法 得到任何数字的。

易混淆数（Confusing Number）指的是一个数字在整体旋转 180° 以后，能够得到一个和原来 不同 的数，且新数字的每一位都应该是有效的。（请注意，旋转后得到的新数字可能大于原数字）

给出正整数 N，请你返回 1 到 N 之间易混淆数字的数量。

示例：

输入：20
输出：6
解释：
易混淆数为 [6,9,10,16,18,19]。
6 转换为 9
9 转换为 6
10 转换为 01 也就是 1
16 转换为 91
18 转换为 81
19 转换为 61

数据范围：

• 1 <= N <= 10^9

思路

用数位$dp$求$[1,N]$中包含$0,1,6,8,9$的数$sum01689$,用$bfs(leetcode248对称中心数Ⅲ)$求$[1,N]$中翻转对称的数$sumpair-1(去掉‘0’)$

答案$res = sum01689-sumpair$
状态表示
$f[pos]$:到$pos$位有多少包含$0,1,6,8,9$的数
状态转移
$f[pos] += dfs(pos-1,lead\&(i==0),limit\&(i==up)) if\quad i\in [0,1,6,8,9]$

typedef long long ll;
class Solution {
public:
    int k[11];
    int f[11];
    int t=0;
    char dl[5]={'1','8','0','9','6'};
    char dr[5]={'1','8','0','6','9'};
    int confusingNumberII(int N) {
        memset(f,-1,sizeof f);
        int cnt = 0,n=N;
        t = N;
        while(n)
        {
            k[++cnt]=n%10;
            n/=10;
        }
        int sum01689 = dfs(cnt,true,true);

        int sumpair = strobogrammaticInRange(to_string(N))-1;
        // cout << sum01689 << sumpair;
        return sum01689-sumpair;
    }
    ll dfs(int pos,bool lead,bool limit)
    {
        if(!pos)return 1;
        if(!lead && !limit && f[pos]!=-1)return f[pos];
        ll res = 0;
        int up = limit?k[pos]:9;
        for(int i=0;i<=up;i++)
        {
            if(i==0||i==1||i==6||i==8||i==9)
                res+=dfs(pos-1,lead&&i==0,limit&&i==up);        
        }
        if(!limit&&!lead)f[pos]=res;
        return res;
    }
    bool larger(string& a,string& b)
    {
        if(a.size()!=b.size())return a.size()>b.size();
        return a>=b;
    }
    int strobogrammaticInRange(string high) {
        queue<string> q;
        string strs[5] = {"","0","1","8"};
        for(auto str:strs)
        {
            q.push(str);
        }
        int res = 0;
        unordered_map<string,int> dic;
        while(q.size())
        {
            string cur = q.front();
            q.pop();
            if(cur.size()<=high.size())
            {
                if(!(cur[0]=='0' && cur.size()>1))
                {
                    if(larger(high,cur) && !dic.count(cur))
                    {
                        dic[cur]=1;
                        res++;
                    }                    
                }
            }
            if(cur.size()>high.size())continue;// 只要比high小 我就可以在两边加
            for(int i=0;i<5;i++)
            {
                string ne = dl[i]+cur+dr[i];
                if(ne.size()>high.size())continue;
                q.push(ne);
            }
        }
        return res;
    }  
};

面试题17.06 2出现的次数

编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。

示例:

输入: 25
输出: 9
解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)

数据范围：

n <= 10^9

typedef long long ll;
class Solution {
public:
    int f[11][2000],k[11];
    int numberOf2sInRange(int n) {
        memset(f,-1,sizeof f);
        int cnt=0,x=n;
        while(x)
        {
            k[++cnt]=x%10;
            x/=10;
        }
        return dfs(cnt,0,true,true);
    }
    ll dfs(int pos,ll sum,bool lead,bool limit)
    {
        if(!pos)return sum;
        if(!lead&&!limit&&f[pos][sum]!=-1)return f[pos][sum];
        ll res=0;
        int up=limit?k[pos]:9;
        for(int i=0;i<=up;i++)
        {
            res+=dfs(pos-1,sum+(i==2),lead&&(i==0),limit&&(i==up));
        }
        if(!lead && !limit)f[pos][sum]=res;
        return res;
    }
};