算法学习之路|数位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;
}
AI 代码解读

例题:

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;
}
AI 代码解读
目录
打赏
0
0
0
0
1243
分享
相关文章
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
120 11
架构学习:7种负载均衡算法策略
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
Java中的算法优化与复杂度分析
在Java开发中,理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略,可以显著提高算法效率。在实际开发中,应该根据具体需求和场景,选择合适的优化方法,从而编写出高效、可靠的代码。
44 6
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
85 1
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。

热门文章

最新文章

目录
目录
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等