算法学习之路|数位dp简要分析-阿里云开发者社区

开发者社区> 人工智能> 正文

算法学习之路|数位dp简要分析

简介: 数位dp简要分析

数位dp一般用于处理一些和数位有关的计数问题,比如说求区间[l,r]中有多少符合条件的数,而为了减少时间复杂度,方法使用的是动态规划的思想。

举例说明:问从0到2345这些数中总共包含多少6。

数位dp的思路是:

1.由于千位是2,首先求出[0,2000)中满足条件的个数,因为此时个十百位可以任意取值,不受上界的限制。

2.之后由于千位已经到达最高,要改为考虑百位,此时百位受到上界的限制,所以之后需要求出[2000,2300)中马满足条件的个数,此时十位和个位不受限制。

3.当百位是3时,十位又受到限制…以此类推。

当然,如何计算一个整百整千的区间的满足条件的个数,也需要在代码中体现,比如这里f(2000)=2f(1000)=2(100+10f(100))=2(100+10(10+10f(10)))

以下是数位dp的模板:

 


#include<stdio.h>
#include<algorithm>
#include<iostream>
#define n 20
using namespace std;
typedef long long ll;
ll dp[n][state];//state作为状态,不同的题目可能有不同的状态个数,有时甚至需要改变dp的维数,第一维代表数的长度
ll dd[n];//将数的每一位存储到数组
ll dfs(int pos,int state,bool lead,bool limit)
/*pos表示当前的数位,此处pos=0表示个位,pos=1表示十位,以此类推
state表示状态参数,也可以有多个状态参数
lead表示前导零(一般来说只有当答案和0有关系时才需要这个参数)
limit表示当前pos位是否受限)*/
{
    if(pos==-1)//表示已经搜索结束
        return 1;//返回并不确定,结合实际情况改变
    if(!lead&&!limit&&dp[pos][state]!=-1)//在不受限的情况下如果dp已被更新,则直接返回
        return dp[pos][state];
    int now=limit?dd[pos]:9;//now用以确定搜索终点,不受限就是9,受限就是当前pos位的数值
    ll ans=0;
    for(int i=0;i<=now;i++)//注意边界
    {
        ans+=dfs(pos-1,newstate,newlead,limit&&i==now);//只有前面所有位数都受限,下一位才受限
    }
    if(!limit&&!lead)//只有当不受限时(即范围为整十,整百...),才更新dp数组,因为受限区间不能代表整区间
        dp[pos][state]=ans;
    return ans;
}

例题:

hdu2089


所有含有4或者含有62的数都是不吉利的,求一定范围内有多少吉利的数。

ac代码:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
ll dp[7][10];
ll dd[7];
ll dfs(int pos,int pre,bool limit)//这里前导零不影响结果,不需要lead   pre表示pos位前一位的数字
{
    if(pos==-1)
        return 1;//进行到这里说明之前位已经全部通过,返回1
    if(!limit&&dp[pos][pre]!=-1)
        return dp[pos][pre];
    int now=limit?dd[pos]:9;
    ll ans=0;
    for(int i=0;i<=now;i++)
    {
        if(i==4||i==2&&pre==6)continue;//是不吉利的数就跳过
        ans+=dfs(pos-1,i,limit&&(i==dd[pos]));
    }
     if(!limit)
        dp[pos][pre]=ans;
    return ans;
}
ll build(int n)//计算从1-n的个数
{
    int k=0;
    while(n)
    {
        dd[k++]=n%10;
        n/=10;
    }
    return dfs(k-1,0,true);
}
int main()
{
    memset(dp,-1,sizeof(dp));//初始化
    int a,b;
    while(scanf("%d%d",&a,&b),a+b)
    {
        printf("%ld\n",build(b)-build(a-1));
    }
    return 0;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章